CodeForces - 1051D Bicolorings(DP)

题目链接：http://codeforces.com/problemset/problem/1051/D

看了大佬的题解后觉着是简单的dp，咋自己做就做不来呢。

大佬的题解：https://www.cnblogs.com/tobyw/p/9685639.html

刚看的时候有点感觉状态肯定是(i,k) 但是这个状态不具备无后效性会受到i-1两个格子啥颜色的影响然后就没往下想了qwq

大佬用了二进制来表示这两格的状态

现在的状态就是(i, k, color) color有4种可能 0，0 1，1 0，1 1，0

状态转移方程就很自然了

dp[i][k][0] = dp[i-1][k][0] + dp[i-1][k][1] +dp[i-1][k][2] + dp[i-1][k-1][3]
dp[i][k][1] = dp[i-1][k-1][0] +dp[i-1][k][1] + dp[i-1][k-2][2] +dp[i-1][k-1][3]
dp[i][k][2] = dp[i-1][k-1][0] + dp[i-1][k-2][1] + dp[i-1][k][2] +dp[i-1][k-1][3]
dp[i][k][3] = (dp[i-1][k-1][0] + dp[i-1][k][1] +dp[i-1][k][2] + dp[i-1][k][3]

代码如下

#include <cstdio>

#include <algorithm>

#define ll long long

#define MOD 998244353

using namespace std;

const int maxn = ;

ll dp[maxn][maxn<<][];

int main(int argc, char const *argv[])

{

    int n, kl;

    scanf("%d%d", &n, &kl);

    dp[][][] = ;

    dp[][][] = dp[][][] = ;

    dp[][][] = ;

    for (int i = ; i <= n; i++) {

        for (int k = ; k <= (i << ); k++) {

            dp[i][k][] = (dp[i-][k][] +

                         dp[i-][k][] +

                          dp[i-][k][] +

                          dp[i-][k-][]) % MOD;

            dp[i][k][] = (dp[i-][k-][] +

                            dp[i-][k][] +

                            dp[i-][k-][] +

                            dp[i-][k-][]) % MOD;

            dp[i][k][] = (dp[i-][k-][] +

                            dp[i-][k-][] +

                            dp[i-][k][] +

                            dp[i-][k-][]) % MOD;

            dp[i][k][] = (dp[i-][k-][] +

                            dp[i-][k][] +

                            dp[i-][k][] +

                            dp[i-][k][]) % MOD;

        }

    }

    printf("%lld\n", (dp[n][kl][] + dp[n][kl][] + dp[n][kl][] + dp[n][kl][]) % MOD);

    return ;

}

巴特西

CodeForces - 1051D Bicolorings(DP)

最新文章

热门文章