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

[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
 
??