下面是官方的解题报告
题意:
给定一个$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种不同的状态转移(见下图)
我的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using namespace std;
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;
}