【題意】：給一塊n*2的巧克力，問分成k塊的方案數(shù)有多少種。
【題解】：多校聯(lián)賽第一場的b，想了2個小時，途中出現(xiàn)MLE,TLE，最后還是AC了。
設(shè)狀態(tài)dp[i][j][0-7]表示處理完第i列已經(jīng)分成j塊且第i列的分割線狀態(tài)為0-7的方案數(shù)。
0：空 1：─ 2：┐ 3：┘ 4：│ 5：┤ 6：
| 7：
| 轉(zhuǎn)移即是延長或終止上一列的分割線或加入新的分割線，具體看代碼。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 const int MOD = 100000007;
26 int dp[2][2010][10];
27 int ans[1010][2010];
28 int n, m;
29
30 void init() {
31 memset(dp, 0, sizeof(dp));
32 dp[0][0][4] = 1;
33 int p3 = 0, p2 = 1;
34 for(int i = 1; i <= 1000; i++) {
35 swap(p3, p2);
36 for(int j = 0; j <= (i << 1); j++)
37 for(int k = 0; k < 8; k++)
38 dp[p3][j][k] = 0;
39 for(int j = 0; j <= (i << 1); j++) {
40 dp[p3][j][0] = (dp[p2][j][0] + dp[p2][j][2] + dp[p2][j][3] + dp[p2][j][4] + dp[p2][j][5]) % MOD;
41 dp[p3][j][1] = (dp[p2][j][1] + dp[p2][j][2] + dp[p2][j][3] + dp[p2][j][4] + dp[p2][j][5] + dp[p2][j][6] + dp[p2][j][7]) % MOD;
42 dp[p3][j][6] = dp[p3][j][7] = (dp[p2][j][0] + dp[p2][j][2] + dp[p2][j][3] + dp[p2][j][4] + dp[p2][j][5]) % MOD;
43 // dp[p3][j][7] = (dp[p2][j][0] + dp[p2][j][2] + dp[p2][j][3] + dp[p2][j][4] + dp[p2][j][5]) % MOD;
44 if(j >= 1) {
45 dp[p3][j][3] = dp[p3][j][2] = (dp[p2][j-1][1] + dp[p2][j-1][2] + dp[p2][j-1][3] + dp[p2][j-1][4] + dp[p2][j-1][5] + dp[p2][j-1][6] + dp[p2][j-1][7]) % MOD;
46 // dp[p3][j][3] = (dp[p2][j-1][1] + dp[p2][j-1][2] + dp[p2][j-1][3] + dp[p2][j-1][4] + dp[p2][j-1][5] + dp[p2][j-1][6] + dp[p2][j-1][7]) % MOD;
47 dp[p3][j][4] = (dp[p2][j-1][0] + dp[p2][j-1][2] + dp[p2][j-1][3] + dp[p2][j-1][4] + dp[p2][j-1][5]) % MOD;
48 }
49 if(j >= 2) dp[p3][j][5] = (dp[p2][j-2][1] + dp[p2][j-2][2] + dp[p2][j-2][3] + dp[p2][j-2][4] + dp[p2][j-2][5] + dp[p2][j-2][6] + dp[p2][j-2][7]) % MOD;
50 ans[i][j] = (dp[p3][j][4] + dp[p3][j][5]) % MOD;
51 }
52 }
53 }
54
55 int main() {
56 int T;
57 init();
58 scanf("%d", &T);
59 while(T--) {
60 scanf("%d%d", &n, &m);
61 printf("%d\n", ans[n][m]);
62 }
63 return 0;
64 }
65