【BZOJ4584】[Apio2016]赛艇 DP

2021-05-06 00:28

阅读：593

标签：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

题解：一开始设的是二维状态，显然不可做啊。。。

先离散化得到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

上一篇：C#中get和set属性的作用

下一篇：路由器的路由配置命令汇总(win和linux系统)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【BZOJ4584】[Apio2016]赛艇 DP
文章链接：http://soscw.com/index.php/essay/82973.html

亲，登录后才可以留言！

【BZOJ4584】[Apio2016]赛艇 DP

【BZOJ4584】[Apio2016]赛艇

Description

Input

Output

Sample Input

Sample Output

评论

热门文章

推荐文章

最新文章

置顶文章