hdu 4301 简单DP

Problem: http://acm.hdu.edu.cn/showproblem.php?pid=4301

长x的巧克力分成y块时，最末端的两小块巧克力可能是分在一块上用DPh[x][y]表示，也可能分在两块上用DPf[x][y]表示

当求DPh[x+1][],DPf[x+1][]时，求可以通过前面的DPh[x][],DPf[x][]上来求值

/*
相同数字表示被分在一起
      x -> x+1
      0    00   01   00   01   01
      0 -> 00 , 01 , 01 , 00 , 02
块数；y    y    y+1  y+1  y+1  y+2
      0    02   01   00   00   02   00   02
      1 -> 12 , 11 , 10 , 11 , 11 , 12 , 13
块数；y    y+1  y    y    y    y+1  y+1  y+2
*/
#include<cstdio>
#define MAXN 1010
#define Mod 100000007//要看清题目，开始习惯性的以为是1000000007 
int DPf[MAXN][MAXN<<1],DPh[MAXN][MAXN<<1];
int main()
{
    int t,n,k;
    scanf("%d",&t);
    DPf[1][2]=DPh[1][1]=1;
    for(int i=2;i<MAXN;i++){
        DPh[i][1]=1;
        for(int j=2;j<=i*2;j++){
            DPh[i][j]=(DPh[i-1][j]+DPh[i-1][j-1]+DPf[i-1][j-1]+DPf[i-1][j]*2)%Mod;
            DPf[i][j]=(DPh[i-1][j-2]+DPh[i-1][j-1]*2+DPf[i-1][j-2]+DPf[i-1][j-1]*2+DPf[i-1][j])%Mod;
        }
    }
    while(t--){
        scanf("%d%d",&n,&k);
        printf("%d
",(DPf[n][k]+DPh[n][k])%Mod);
    }
    return 0;
}

View Code

这是一个与实际不协调的问题，巧克力带这么分的么.....NC