BZOJ1037 ZJOI2008生日聚会（动态规划）

　　设f[i][j][x][y]为安排了i个男孩j个女孩，后缀最大男孩-女孩数为x，最大女孩-男孩数为y的方案数。转移显然。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 151

#define M 22

#define P 12345678

int n,m,k,f[N][N][M][M];

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj1037.in","r",stdin);

    freopen("bzoj1037.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),k=read();

    f[][][][]=;

    for (int i=;i<=n+m;i++)

        for (int j=max(,i-m);j<=min(n,i);j++)

        {

            int x=j,y=i-j;

            for (int p=;p<=min(k,x);p++)

                for (int q=;q<=min(k,y);q++)

                {

                    if (x&&p)

                    {

                        inc(f[x][y][p][q],f[x-][y][p-][q+]);

                        if (q==) inc(f[x][y][p][q],f[x-][y][p-][q]);

                    }

                    if (y&&q)

                    {

                        inc(f[x][y][p][q],f[x][y-][p+][q-]);

                        if (p==) inc(f[x][y][p][q],f[x][y-][p][q-]);

                    }

                }

        }

    int ans=;

    for (int i=;i<=k;i++)

        for (int j=;j<=k;j++)

        inc(ans,f[n][m][i][j]);

    cout<<ans;

    return ;

}