http://acm.hdu.edu.cn/showproblem.php?pid=4301
题意：
有一块n*2大小的巧克力，现在某人要将这巧克力分成k个部分，每个部分大小随意，问有多少种分法。
思路：
dp [ i ] [ j ] [ 0/1 ]表示到第 i 列时分成 j 块的方案数，0/1表示第 i 列的两格巧克力是否相连。
这样的话，分析到第 i 块时的情况如下：
①块数不变
dp[i][j][] = dp[i][j][] + dp[i-][j][]*
dp[i][j][] = dp[i-][j][]
②块数+1
dp[i][j][] = dp[i-][j-][] + dp[i-][j-][]
dp[i][j][] = dp[i-][j-][]* + dp[i-][j-][]*
③块数+2
dp[i][j][] = dp[i-][j-][] + dp[i-][j-][]
最后加起来即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int mod = ; int n, k;
int dp[][][]; int main()
{
dp[][][] = ;
dp[][][] = ;
dp[][][] = ;
dp[][][] = ;
for(int i=;i<=;i++)
{
for(int j=;j<=*i;j++)
{
dp[i][j][] += dp[i-][j][] + dp[i-][j][]*;
dp[i][j][]%=mod;
dp[i][j][] += dp[i-][j][];
dp[i][j][]%=mod;
dp[i][j][] += dp[i-][j-][] + dp[i-][j-][];
dp[i][j][]%=mod;
dp[i][j][] += dp[i-][j-][]* + dp[i-][j-][]*;
dp[i][j][]%=mod;
if(j>)
{
dp[i][j][] += dp[i-][j-][] + dp[i-][j-][];
dp[i][j][]%=mod;
}
}
}
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
printf("%d\n",(dp[n][k][]+dp[n][k][])%mod);
}
return ;
}