题目描述
咳咳,懒得复制了上面是两张图:)
解题思路
这题是一道很好的题,感觉之前做过,一开始手推状态找规律,可以用状压但是没想到
借鉴了一下大佬的dp
modify数组用以累加新增的状态数
dp数组表示前i列第j个连通块,a,b表示该列的状态,转移方程见代码
下面就是美丽的代码了
AC Code
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define P (LL)(998244353) typedef long long LL; typedef long double ld; typedef unsigned long long ULL; using namespace std; const int MAXN = 1000 + 10; const int MAXK = MAXN << 1; int dp[MAXN][MAXK][2][2]; int modify[2][2][2][2]; void pre() { modify[0][0][0][0] = 0; modify[0][0][0][1] = 1; modify[0][0][1][1] = 1; modify[0][0][1][0] = 1; modify[0][1][0][0] = 0; modify[0][1][0][1] = 0; modify[0][1][1][0] = 2; modify[0][1][1][1] = 0; modify[1][0][0][0] = 0; modify[1][0][0][1] = 2; modify[1][0][1][0] = 0; modify[1][0][1][1] = 0; modify[1][1][0][0] = 1; modify[1][1][0][1] = 1; modify[1][1][1][0] = 1; modify[1][1][1][1] = 0; } int main() { int n , k; cin>>n>>k; pre(); dp[1][2][0][1] = dp[1][2][1][0] = 1; dp[1][1][1][1] = dp[1][1][0][0] = 1; for(int i = 2; i <= n; i++) for(int j = 1; j <= k; j++) for(int a = 0; a < 2; a++) for(int b = 0; b < 2; b++) for(int A = 0; A < 2; A++) for(int B = 0; B < 2; B++) { int block = modify[A][B][a][b]; if(j >= block) dp[i][j][a][b] = (dp[i][j][a][b] + dp[i - 1][j - block][A][B]) % P; } int ans = 0; for(int A = 0; A < 2; A++) for(int B = 0; B < 2; B++) ans = (ans + dp[n][k][A][B]) % P; cout<<ans; return 0; }