【BZOJ1037】[ZJOI2008]生日聚会（动态规划）

题面

题解

假设前面的都合法，但是在加完当前的最后一个人之后变得不合法了，那么意味着一定有着一个后缀不合法。把男生看成\(1\)，女生看成\(-1\)，也就是不存在一个后缀和大于\(K\)或者一个后缀和小于\(-K\)。而在最后面加进一个男生或者女生显然就是把所有后缀\(+1\)或者\(-1\)。那么设\(f[i][j][k][l]\)表示当前考虑到了第\(i\)个位置，放了\(j\)个\(1\)，最大的后缀和为\(j\)，最小的后缀和为\(-l\)的方案数。转移的时候判断一下是否合法就好了。

时间复杂度\(O(n^2k^2)\)。

#include<iostream>

#include<cstdio>

using namespace std;

#define MOD 12345678

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

int f[305][155][22][22];

int n,m,K,ans;

int main()

{

	scanf("%d%d%d",&n,&m,&K);

	f[0][0][0][0]=1;

	for(int i=1;i<=n+m;++i)

		for(int j=0;j<=i&&j<=n;++j)

			for(int k=0;k<=K;++k)

				for(int l=0;l<=K;++l)

				{

					if(!f[i-1][j][k][l])continue;

					if(j<n&&k!=K)add(f[i][j+1][k+1][max(0,l-1)],f[i-1][j][k][l]);

					if(i-j-1<m&&l!=K)add(f[i][j][max(0,k-1)][l+1],f[i-1][j][k][l]);

				}

	for(int k=0;k<=K;++k)

		for(int l=0;l<=K;++l)

			add(ans,f[n+m][n][k][l]);

	printf("%d\n",ans);

	return 0;

}

巴特西

【BZOJ1037】[ZJOI2008]生日聚会（动态规划）

【BZOJ1037】[ZJOI2008]生日聚会（动态规划）

题面

题解

最新文章

热门文章