[BZOJ 1037][ZJOI2008]生日聚会Party(DP)

?

题目太神了，给跪。。。。

这题完全想不到dp的思路，网上的题解翻来翻去也没几个靠谱的，最终总算找到了个靠谱点的题解想明白了。。。

首先，我们把这个题目简化下，相当于给你n个0，m个1，要你排列它们，使得任意连续的序列中0个数和1的个数之差小于等于K

然后我们就用f[a][b][c][d]表示当前有a个0，b个1，0比1最多多k个，1比0最多多t个的方案数

dp过程中，每加入一个新的数，我们既可以加0，也可以加1。

加0的前提是剩下的数中有0，而且当前0比1多不到k个

加1的前提是剩下的数中有0，而且当前1比0多不到k个

最终我们再统计答案，把0比1多i个、1比0多j个的所有合法方案的个数加起来。

这就是这道题的全过程了

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define MAXN 155 #define MAXM 22 #define MOD 12345678 using namespace std; int f[MAXN][MAXN][MAXM][MAXM]; //f[a][b][c][d]=a个0，b个1，0比1最多多k个，1比0最多多t个的方案数 int n,m,K,ans; int main() { scanf(%d%d%d,&n,&m,&K); f[0][0][0][0]=1; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=K;k++) for(int t=0;t<=K;t++) { if(f[i][j][k][t]) { if(i
       
        
?
 ??