HDU 4301 Divide Chocolate

这个题在暑假集训的时候做组队训练赛的时候做过，当时状态方程是我推出来的，但是WA了10+次吧。但是这次写，还是WA了很多次。

所以总结一下，DP的话，能用递推写还是尽量用递推写吧，记忆化写的话可能会出现问题，这个应该是我水平问题吧。

方程是这样的:dp(i,j,1) = (dp(i - 1,j - 2,1) + dp(i - 1,j - 1,1) * 2 + dp(i - 1,j,1) + dp(i - 1,j - 2,0) + dp(i - 1,j - 1,0) * 2) % MOD;

dp(i,j,0) = (dp(i - 1,j,0) + dp(i - 1,j - 1,0) + dp(i - 1,j - 1,1)+ dp(i - 1,j,1) * 2) % MOD;

dp(i,j,0)表示当切到第i层切到j块时第i层中间的巧克力是不连着的切法的总数。

dp(i,j,1)表示当切到第i层切到j块时第i层中间的巧克力是连着的切法的总数。

下面贴代码吧：

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 #define MOD 100000007
 6 int d[1020][2040][2];
 7 
 8 int dp(int i,int j,int k)
 9 {
10     if(j <= 0)  return 0;
11 
12     int &ans = d[i][j][k];
13 
14     if(ans != -1)   return ans;
15 
16     if(i * 2 < j)
17     {
18         ans = 0;
19         return ans;
20     }
21 
22     if(k == 1)
23     {
24         ans = (dp(i - 1,j - 2,1) + dp(i - 1,j - 1,1) * 2 + dp(i - 1,j,1)
25                 + dp(i - 1,j - 2,0) + dp(i - 1,j - 1,0) * 2) % MOD;
26         return ans;
27     }
28 
29     else if(k == 0)
30     {
31         ans = (dp(i - 1,j,0) + dp(i - 1,j - 1,0) + dp(i - 1,j - 1,1)
32          + dp(i - 1,j,1) * 2) % MOD;
33         return ans;
34     }
35 }
36 
37 int main()
38 {
39     int ncase,n,k;
40     scanf("%d",&ncase);
41     memset(d,-1,sizeof(d));
42     d[1][1][0] = 1;
43     d[1][1][1] = 0;
44     d[1][2][0] = 0;
45     d[1][2][1] = 1;
46     while(ncase--)
47     {
48         scanf("%d%d",&n,&k);
49         printf("%d\n",(dp(n,k,0) + dp(n,k,1)) % MOD);
50     }
51     return 0;
52 }