首页 > 代码库 > BZOJ 1037 生日聚会Party（DP）
BZOJ 1037 生日聚会Party（DP）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1037
题意:给定n个0m个1。有多少种排列方式使得任意一段中01的个数差小于等于K？
思路：f[i][j][k][t]表示i个0、j个1、0比1最多多k个、1比0最多多t的方案数。
int n,m,K,f[N][N][21][21];void up(int &x,int y){ x+=y; if(x>=mod) x-=mod;}int main(){ RD(n,m,K); int i,j,k,t; f[0][0][0][0]=1; FOR0(i,n+1) FOR0(j,m+1) FOR0(k,K+1) FOR0(t,K+1) if(f[i][j][k][t]) { if(i<n&&k<K) up(f[i+1][j][k+1][max(t-1,0)],f[i][j][k][t]); if(j<m&&t<K) up(f[i][j+1][max(k-1,0)][t+1],f[i][j][k][t]); } int ans=0; FOR0(i,K+1) FOR0(j,K+1) up(ans,f[n][m][i][j]); PR(ans); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。