BZOJ 1037:[ZJOI 2008]バースデーパーティーParty
7266 ワード
DP…
1 /**************************************************************
2 Problem: 1037
3 User: zhuohan123
4 Language: C++
5 Result: Accepted
6 Time:448 ms
7 Memory:1792 kb
8 ****************************************************************/
9
10 #include <iostream>
11 #include <cstdio>
12 #include <cstring>
13 using namespace std;
14 inline int imax(int a,int b){return a>b?a:b;}
15 inline int imin(int a,int b){return a<b?a:b;}
16 const int mo=12345678;
17 inline int add(int &a,int b){a=(a+b)%mo;}
18 int f[2][151][21][21];
19 //f[ ][ ][ - ][ - ] P.S. 0
20 int main(int argc, char *argv[])
21 {
22 int n,m,k;cin>>n>>m>>k;
23 f[0][0][0][0]=1;
24 for(int i=0;i<n+m;i++)
25 {
26 memset(f[(i+1)&1],0,sizeof f[(i+1)&1]);
27 for(int j=0;j<=imin(i,n);j++)
28 for(int bmg=0;bmg<=imin(j,k);bmg++)
29 for(int gmb=0;gmb<=imin(i-j,k);gmb++)
30 {
31 if(bmg<k&&j<n)add(f[(i+1)&1][j+1][bmg+1][imax(gmb-1,0)],f[i&1][j][bmg][gmb]);
32 if(gmb<k&&(i-j)<m)add(f[(i+1)&1][j][imax(bmg-1,0)][gmb+1],f[i&1][j][bmg][gmb]);
33 }
34 }
35 int ans=0;
36 for(int i=0;i<=k;i++)
37 for(int j=0;j<=k;j++)
38 add(ans,f[(n+m)&1][n][i][j]);
39 cout<<ans<<endl;
40 return 0;
41 }