BZOJ 1037 生日聚会

题意

n个男生m个女生排成一排，要求任意一段男生和女生人数差不超过k，求排列方案数。（假设所有男生都一样，所有女生都一样）答案取模。

数据范围

$$n,m\leqslant150\ \ \ ;\ \ \ k\leqslant20$$

题解

数据这么小，一想就是DP，但没想到是四维的……
f[i][j][x][y]表示前i个人中有j个男生，且从后面起男生最多比女生多x个，女生最多比男生多y个。
f[i+1][j+1][x+1][max(y-1,0)]+=f[i][j][x][y];（队列最后加一男生）
f[i+1][j][max(x-1,0)][y]+=f[i][j][x][y];（队列最后加一女生）

代码

#include<cstdio>
const int mod=12345678;
int f[301][151][21][21];
int MAX(int x,int y) {if (x>y) return x; return y;}
int main()
{
	int n,m,k,ans=0;
	scanf("%d%d%d",&n,&m,&k);
	f[0][0][0][0]=1;
	for (int i=0;i<m+n;i++)
	for (int j=0;j<=n;j++)
	for (int x=0;x<=k;x++)
	for (int y=0;y<=k;y++)
	if (f[i][j][x][y])
	{
		if (x+1<=k&&j+1<=n)
			f[i+1][j+1][x+1][MAX(y-1,0)]=(f[i+1][j+1][x+1][MAX(y-1,0)]+f[i][j][x][y])%mod;
		if (y+1<=k&&i-j+1<=m)
			f[i+1][j][MAX(x-1,0)][y+1]=(f[i+1][j][MAX(x-1,0)][y+1]+f[i][j][x][y])%mod;
	}
	
	for (int x=0;x<=k;x++)
	for (int y=0;y<=k;y++)
		ans=(ans+f[n+m][n][x][y])%mod;
	printf("%d",ans);
	return 0;
}