hdu4301 Divide Chocolate 动态规划解题报告（多校1）

下面是官方的解题报告

题意：

给定一个$2n$的矩形，求把这个矩形分割为$k$部分的方法，且对称的切割方法视为不同，输出时模上$100000007$。

($1 \leq n \leq 1000,1 \leq k \leq 2n$)

解法：

看到这个题目，很容易想到DP。

状态表示

$f_{i0j}$ :前$i$行已经出现了$j$部分且第$i$行的两个格子属于同一部分的方法数
$f_{i1j}$ :前$i$行已经出现了$j$部分且第$i$行的两个格子属于不同部分的方法数

初始条件

$f_{101} = f_{112} = 1$

状态转移,下面使用$I$表示$i+1$,$J$表示$j+1$,$jj$表示$j+2$

$f_{I0j}=f_{I0j}+f_{i0j}+2f_{i1j}$
$f_{I0J}=f_{I0J}+f_{i0j}+f_{i1j}$
$f_{I1j}=f_{I1j}+f_{i1j}$
$f_{I1J}=f_{I1J}+2f_{i0j}+2f_{i1j}$
$f_{I1jj}=f_{I1jj}+f_{i0j}+f_{i1j}$

共12种不同的状态转移（见下图）

我的代码

hdu4301 Divide Chocolateview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

int dp[2][1005][2010];
const int mod = 100000007;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,k,i,j;
        scanf("%d%d",&n,&k);
        zero(dp);
        for(i=1;i<=n;i++)
            dp[0][i][1]=1,dp[1][i][1]=0;
        dp[1][1][2]=1;
        for(i=2;i<=n;i++)
        {
            for(j=2;j<=2*i&&j<=k;j++)
            {
                dp[0][i][j]=( dp[0][i-1][j-1] + dp[0][i-1][j] + dp[1][i-1][j-1] + dp[1][i-1][j]*2 ) % mod;
                dp[1][i][j]=( dp[0][i-1][j-1]*2 +dp[0][i-1][j-2]+ dp[1][i-1][j-1]*2 + dp[1][i-1][j] + dp[1][i-1][j-2]) % mod;
            }
        }
        printf("%d\n",(dp[0][n][k]+dp[1][n][k])%mod);
    }
    return 0;
}