【BZOJ4584】[Apio2016]赛艇 DP
标签：char 离散化 ace min space 二维 nod long ++
【BZOJ4584】[Apio2016]赛艇
Description
在首尔城中，汉江横贯东西。在汉江的北岸，从西向东星星点点地分布着个划艇学校，编号依次为到。每个学校都拥有若干艘划艇。同一所学校的所有划艇颜色相同，不同的学校的划艇颜色互不相同。颜色相同的划艇被认为是一样的。每个学校可以选择派出一些划艇参加节日的庆典，也可以选择不派出任何划艇参加。如果编号为的学校选择派出划艇参加庆典，那么，派出的划艇数量可以在Ai至Bi之间任意选择（Ai
Input
第一行包括一个整数N，表示学校的数量。接下来N行，每行包括两个正整数，用来描述一所学校。其中第行包括的两个正整数分别表示Ai,Bi（1
Output
输出一行，一个整数，表示所有可能的派出划艇的方案数除以1,000,000,007得到的余数
Sample Input
2
1 2
2 3
Sample Output
7
题解：一开始设的是二维状态，显然不可做啊。。。
先离散化得到2*n个区间，然后用f[i][j][k]表示前i个学校，最后一个学校的数量在第j个区间中，并且第j个区间中已经有k个数的方案数。
如果上一个学校与当前学校不再同一个区间，那么我们维护s[j]表示$\sum\limits_{l
如果采用01背包式的枚举顺序，在空间上可以省掉一维。
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll P=1000000007;
int n,m;
ll ans;
int A[510],B[510],siz[1010];
ll ref[1010],f[1010][510],s[1010],ine[510];
struct node
{
int val,org;
}num[1010];
bool cmp(node a,node b)
{
return a.val‘9‘) {if(gc==‘-‘) f=-f; gc=getchar();}
while(gc>=‘0‘&&gcnum[i-1].val) ref[++m]=num[i].val;
if(!A[num[i].org]) A[num[i].org]=m+1;
else B[num[i].org]=m;
}
ine[1]=1;
for(i=2;i=A[i];j--)
{
siz[j]=min(ref[j]-ref[j-1],siz[j]+1ll);
for(k=siz[j];k>=2;k--) f[j][k]=(f[j][k]+f[j][k-1]*(ref[j]-ref[j-1]-k+1)%P*ine[k])%P;
f[j][1]=(f[j][1]+s[j-1]*(ref[j]-ref[j-1]))%P;
}
}
for(i=1;i
【BZOJ4584】[Apio2016]赛艇 DP
标签：char 离散化 ace min space 二维 nod long ++
原文地址：http://www.cnblogs.com/CQzhangyu/p/7670345.html
评论