学步园

题意：给定2*n的巧克力，想把它分成k份，问一共有多少种方法数。

题解：很容易想到dp，因为到最后一行的时候两块巧克力是否属于同一组，考虑dp[i][j][0]代表到i行已经分成j块且最后一行两块属于同一部分的方法数，
           dp[i][j][1]代表到i行已经分成j块且最后一行两块不属于同一部分的方法数，一共有12中转移方法：然后预处理出dp后求解。



Sure原创，转载请注明出处。

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn = 1002;
const int mod = 100000007;
int dp[maxn][maxn << 1][2];
int n,k;

void init()
{
    memset(dp,0,sizeof(dp));
    dp[1][1][0] = dp[1][2][1] = 1;
    for(int i=1;i<1000;i++)
    {
        for(int j=1;j<2000;j++)
        {
            dp[i+1][j][0] += dp[i][j][0];
            dp[i+1][j][0] %= mod;

            dp[i+1][j+1][0] += dp[i][j][0];
            dp[i+1][j+1][0] %= mod;

            dp[i+1][j+1][1] += (dp[i][j][0] << 1);
            dp[i+1][j+1][1] %= mod;

            dp[i+1][j+2][1] += dp[i][j][0];
            dp[i+1][j+2][1] %= mod;

            dp[i+1][j][0] += (dp[i][j][1] << 1);
            dp[i+1][j][0] %= mod;

            dp[i+1][j][1] += dp[i][j][1];
            dp[i+1][j][1] %= mod;

            dp[i+1][j+1][0] += dp[i][j][1];
            dp[i+1][j+1][0] %= mod;

            dp[i+1][j+1][1] += (dp[i][j][1] << 1);
            dp[i+1][j+1][1] %= mod;

            dp[i+1][j+2][1] += dp[i][j][1];
            dp[i+1][j+2][1] %= mod;
        }
    }
    return;
}

void solve()
{
    scanf("%d %d",&n,&k);
    if(k > (n << 1)) puts("0");
    else if(k == (n << 1)) puts("1");
    else printf("%d\n",(dp[n][k][0] + dp[n][k][1]) % mod);
    return;
}

int main()
{
    init();
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        solve();
    }
    return 0;
}