首页 > ACM题库 > HDU-杭电 > HDU 4301-Divide Chocolate-动态规划-[解题报告]HOJ
2015
05-23

HDU 4301-Divide Chocolate-动态规划-[解题报告]HOJ

Divide Chocolate

问题描述 :

It is well known that claire likes dessert very much, especially chocolate. But as a girl she also focuses on the intake of calories each day. To satisfy both of the two desires, claire makes a decision that each chocolate should be divided into several parts, and each time she will enjoy only one part of the chocolate. Obviously clever claire can easily accomplish the division, but she is curious about how many ways there are to divide the chocolate.
Clairewd’s message

To simplify this problem, the chocolate can be seen as a rectangular contains n*2 grids (see above). And for a legal division plan, each part contains one or more grids that are connected. We say two grids are connected only if they share an edge with each other or they are both connected with a third grid that belongs to the same part. And please note, because of the amazing craft, each grid is different with others, so symmetrical division methods should be seen as different.

输入:

First line of the input contains one integer indicates the number of test cases. For each case, there is a single line containing two integers n (1<=n<=1000) and k (1<=k<=2*n).n denotes the size of the chocolate and k denotes the number of parts claire wants to divide it into.

输出:

First line of the input contains one integer indicates the number of test cases. For each case, there is a single line containing two integers n (1<=n<=1000) and k (1<=k<=2*n).n denotes the size of the chocolate and k denotes the number of parts claire wants to divide it into.

样例输入:

2
2 1
5 2

样例输出:

1
45

题目:hdu 4301 Divide Chocolate

题意:2*n的巧克力分成k份的方案数

思路:跟铺砖的是一样的

用dp[i][j][k]表示前i-1列已经处理好了,i列切成j块,k=0表示第i列两块属于同一部分,k=1表示第i列两块不属于同一部分。

这里列出第i+1列和第i列的状态,用数字区别不同

Divide Chocolate

#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
#define mod 100000007
#define maxn 1010
int dp[maxn][2030][2];
int main()
{
    memset(dp,0,sizeof(dp));
    dp[1][1][0]=1;
    dp[1][1][1]=0;
    dp[1][2][1]=1;
    dp[1][2][0]=0;
    for(int i=2;i<maxn;i++)
    {
        for(int j=1;j<2*maxn;j++)
        {
            dp[i][j][0]=(dp[i-1][j][0]+2*dp[i-1][j][1]+dp[i-1][j-1][0]+dp[i-1][j-1][1])%mod;
            if(j>=2)
                dp[i][j][1]=(2*dp[i-1][j-1][0]+dp[i-1][j][1]+2*dp[i-1][j-1][1]+dp[i-1][j-2][0]+dp[i-1][j-2][1])%mod;
            else
                dp[i][j][1]=(2*dp[i-1][j-1][0]+dp[i-1][j][1]+2*dp[i-1][j-1][1])%mod;
        }
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        printf("%d\n",(dp[n][k][0]+dp[n][k][1])%mod);
    }
    return 0;
}

                  

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/shiyuankongbu/article/details/12614713