Codeforces 1051D(状压DP)

发表于 | 分类于 | | + s

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个甚至很多个，可以使用状压的方法。

#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;
}
------ 本文结束 ------