cf1051d 简单的状态压缩dp

/* 给定一个二行n列的格子，在里面填黑白色，要求通过黑白色将格子分为k块 请问有多少种填色方式 dp[j][k][0,1,2,3] 填到第j列，有k块，第j列的颜色， */ #include<bits/stdc++.h> using namespace std; #define ll long long #define mod 998244353 //0全白，1黑白，2白黑，3黑黑 ll dp[1050][1050*2][4],n,k; int main(){ cin>>n>>k; memset(dp,0,sizeof dp); dp[1][1][0]=dp[1][1][3]=1; dp[1][2][1]=dp[1][2][2]=1; for(int i=2;i<=n;i++) for(int j=1;j<=k;j++){ dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j-1][3]+dp[i-1][j][1]+dp[i-1][j][2])%mod; dp[i][j][3]=(dp[i-1][j-1][0]+dp[i-1][j][3]+dp[i-1][j][1]+dp[i-1][j][2])%mod; dp[i][j][1]=(dp[i-1][j-1][0]+dp[i-1][j-1][3]+dp[i-1][j][1]+dp[i-1][j-2][2])%mod; dp[i][j][2]=(dp[i-1][j-1][0]+dp[i-1][j-1][3]+dp[i-1][j-2][1]+dp[i-1][j][2])%mod; } printf("%lld\n",(dp[n][k][0]+dp[n][k][1]+dp[n][k][2]+dp[n][k][3])%mod); }

 

转载于:https://www.cnblogs.com/zsben991126/p/10372422.html