Codeforces 1051D(状压DP)

Codeforces 1051D
题意:给一个$2$行$n$列的矩阵填上黑色和白色,求连通块个数为$k$个的填色方案数量。
好像这题和之前 edu 一题很像……
刚开始可以想到$dp(i,j,k)$为第$i$行第$j$列有$k$个连通分量的方案数,但是转移比较困难,不知道前面那一列的颜色,用包含行的状态也不好进行转移,所以我们要删去行的状态,增加颜色的状态,这里可以利用状压 DP 思想将最后一行状态压起来,问题就基本上能解决了。
$dp(j, k, st)$表示前$j$列有$k$个连通分量,$j$列的状态为$st$的方案数,然后转移即可。
具体转移看代码即可,太长了……
知识点:
1、DP 状态如果不方便转移,要想一想为什么不方便转移,是否能增加状态或者排序贪心等。增加状态也不一定只能增加一个,可以增加2个甚至很多个,可以使用状压的方法。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const LL MO = 998244353, MAXN = 2005;
const LL st00 = 0, st01 = 1, st10 = 2, st11 = 3;
LL n, k, dp[MAXN][MAXN][5];
void clean() {
ms(dp, 0);
}
int solve() {
clean();
dp[1][1][st00] = dp[1][1][st11] = dp[1][2][st01] = dp[1][2][st10] = 1;
for (LL j = 2; j <= n; j++) {
for (LL x = 0; x <= k; x++) {
if (x - 2 >= 0)
dp[j][x][st01] = (dp[j][x][st01] + dp[j - 1][x - 2][st10]) % MO;
if (x - 1 >= 0)
dp[j][x][st01] = (dp[j][x][st01] + dp[j - 1][x - 1][st11]) % MO,
dp[j][x][st01] = (dp[j][x][st01] + dp[j - 1][x - 1][st00]) % MO;
dp[j][x][st01] = (dp[j][x][st01] + dp[j - 1][ x ][st01]) % MO;
if (x - 2 >= 0)
dp[j][x][st10] = (dp[j][x][st10] + dp[j - 1][x - 2][st01]) % MO;
if (x - 1 >= 0)
dp[j][x][st10] = (dp[j][x][st10] + dp[j - 1][x - 1][st11]) % MO,
dp[j][x][st10] = (dp[j][x][st10] + dp[j - 1][x - 1][st00]) % MO;
dp[j][x][st10] = (dp[j][x][st10] + dp[j - 1][ x ][st10]) % MO;
dp[j][x][st00] = (dp[j][x][st00] + dp[j - 1][ x ][st10]) % MO;
if (x - 1 >= 0)
dp[j][x][st00] = (dp[j][x][st00] + dp[j - 1][x - 1][st11]) % MO;
dp[j][x][st00] = (dp[j][x][st00] + dp[j - 1][ x ][st01]) % MO;
dp[j][x][st00] = (dp[j][x][st00] + dp[j - 1][ x ][st00]) % MO;
dp[j][x][st11] = (dp[j][x][st11] + dp[j - 1][ x ][st10]) % MO;
if (x - 1 >= 0)
dp[j][x][st11] = (dp[j][x][st11] + dp[j - 1][x - 1][st00]) % MO;
dp[j][x][st11] = (dp[j][x][st11] + dp[j - 1][ x ][st01]) % MO;
dp[j][x][st11] = (dp[j][x][st11] + dp[j - 1][ x ][st11]) % MO;
}
}
printf("%lld\n", (dp[n][k][st00] + dp[n][k][st11] + dp[n][k][st01] + dp[n][k][st10]) % MO);
return 0;
}
int main() {
scanf("%lld%lld", &n, &k), solve();
return 0;
}

------ 本文结束 ------