BZOJ 1037: [ZJOI2008]生日聚会Party 动态规划

code: 

#include <cstdio> 
#include <cstring> 
#include <algorithm>   
#define ll long long 
#define MAXN 160 
#define MAXK 20   
#define mod 12345678   
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int dp1[MAXN+10][MAXK+2][MAXK+2],dp2[MAXN+10][MAXK+2][MAXK+2];   
int main() 
{ 
    // setIO("input");  
    int i,j,n,m,k; 
    scanf("%d%d%d",&n,&m,&k);   
    int sum=n+m;  
    dp1[0][0][0]=1;    
    for(i=0;i<sum;++i) 
    {
        swap(dp1,dp2);    
        memset(dp1,0,sizeof(dp1));     
        for(j=0;j<=min(i,m);++j) 
        {
            for(int k1=0;k1<=k;++k1) 
            {
                for(int k2=0;k2<=k;++k2) 
                {
                    dp1[j+1][max(k1-1,0)][k2+1]+=dp2[j][k1][k2];   
                    dp1[j][k1+1][max(k2-1,0)]+=dp2[j][k1][k2];     
                    dp1[j][k1][k2]%=mod;   
                }
            }
        }
    }
    int ans=0;     
    for(int k1=0;k1<=k;++k1) 
    {
        for(int k2=0;k2<=k;++k2) 
        {
            ans=(ans+dp1[m][k1][k2])%mod;   
        }
    }
    printf("%d
",ans);   
    return 0; 
}