CodeForces - 1051D (线性DP) - Lis~
CodeForces – 1051D (线性DP)
题目：https://codeforces.com/problemset/problem/1051/D
题意：一个2行n列的矩形，上面有黑白块，然后问你怎么布置才能有k个连通块，问有多少种方案数
思路：其实就是一个矩阵，我们一次放一列
四种状态
黑 | 白 | 白 | 黑
白 | 黑 | 白 | 黑
我们dp[n][m][k],第n列第m种状态k个连通块的方案数，现在我们算放每个状态时，计算一次增加了多少个连通块
因为数组太大了，所以我们用滚动数组
然后递推就行了
#include<bits/stdc++.h> #define maxn 2005 #define mod 998244353 using namespace std; typedef long long ll; ll dp[2][4][maxn]; ll n,k; int main(){ cin>>n>>k; dp[0][0][2]=1;// 0 1 dp[0][1][2]=1;// 1 0 dp[0][2][1]=1;// 1 1 dp[0][3][1]=1;// 0 0 for(int i=2;i<=n;i++){ for(int j=0;j<=k;j++){ dp[1][0][j]=dp[0][0][j]; dp[1][1][j]=dp[0][1][j]; dp[1][2][j]=((dp[0][0][j]+dp[0][1][j])%mod+dp[0][2][j])%mod; dp[1][3][j]=((dp[0][0][j]+dp[0][1][j])%mod+dp[0][3][j])%mod; if(j-2>=0){ dp[1][0][j]=(dp[1][0][j]+dp[0][1][j-2])%mod; dp[1][1][j]=(dp[1][1][j]+dp[0][0][j-2])%mod; } if(j-1>=0){ dp[1][2][j]=(dp[1][2][j]+dp[0][3][j-1])%mod; dp[1][3][j]=(dp[1][3][j]+dp[0][2][j-1])%mod; dp[1][0][j]=((dp[1][0][j]+dp[0][2][j-1])%mod+dp[0][3][j-1])%mod; dp[1][1][j]=((dp[1][1][j]+dp[0][2][j-1])%mod+dp[0][3][j-1])%mod; } } for(int j=0;j<=k;j++){ for(int z=0;z<=3;z++){ dp[0][z][j]=dp[1][z][j]; dp[1][z][j]=0; } } } ll sum=((dp[0][0][k]+dp[0][1][k])%mod+(dp[0][2][k]+dp[0][3][k])%mod)%mod; printf("%lld",sum); }
版权声明：本文为Lis-原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。