题目链接：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 ;
}