BZOJ-1037: [ZJOI2008]生日聚会Party（D

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1037

动态规划：

状态：f(i,j,x,y)表示已经选取好了1..i的人，然后有j个男生，从某一位置起到i的序列中男生比女生最多多x人，女生比男生最多多y人，(x,y>=0),然后状态转移：

f(i+1,j+1,x+1,y-1)+=f(i,j,x,y) 第i+1是男生 (x+1<=k,j+1<=n)

f(i+1,j,x-1,y+1)+=f(i,j,x,y) 第i+1是女生(y+1<=k,i+1-j<=m)

（貌似说空间没有丧心病狂地卡到要滚动数组啊，为什么网上大神们都这么说...）

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
#define MAXN 151
#define MAXK 21
#define inf 0x7fffffff
#define MAX 12345678
 
int n,m,k,f[MAXN+MAXN][MAXN][MAXK][MAXK];
 
int main() {
    scanf("%d%d%d",&n,&m,&k);
    memset(f,0,sizeof(f));
    f[0][0][0][0]=1;
    for (int i=0;i<n+m;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][j][x][y];
                            f[i+1][j+1][x+1][max(y-1,0)]%=MAX;
                        }
                        if (y+1<=k&&i+1-j<=m) {
                            f[i+1][j][max(x-1,0)][y+1]+=f[i][j][x][y];
                            f[i+1][j][max(x-1,0)][y+1]%=MAX;
                        }
                    }
                }
            }
        }
    }
    int ans=0;
    for (int i=0;i<=n;i++) {
        for (int x=0;x<=k;x++) {
            for (int y=0;y<=k;y++) {
                ans+=f[n+m][i][x][y];
                ans%=MAX;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}