题解：CF1051D Bicolorings

动态规划，很有思维含量。

首先看到题还以为打表找规律，但是规律好像是没有的。

注意到棋盘宽为二，那每次往右边摆两个就有四种方式：黑黑，黑白，白黑，白白。那就可以将

dp_{i,j,k}

表示为前

i

列有

j

个连通块时当前为第

k

种摆法的方案数。

初始化：

CPP

dp[1][1][1]=1;
dp[1][2][2]=1;
dp[1][2][3]=1;
dp[1][1][4]=1;

转移方式推的时候可以画图便于推式：

CPP

//1:X 2:X 3:. 4:.
//X   .   X   .
dp[i][j][1]+=dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][3]+dp[i-1][j-1][4];
dp[i][j][2]+=dp[i-1][j-1][1]+dp[i-1][j][2]+dp[i-1][j-2][3]+dp[i-1][j-1][4];
dp[i][j][3]+=dp[i-1][j-1][1]+dp[i-1][j-2][2]+dp[i-1][j][3]+dp[i-1][j-1][4];
dp[i][j][4]+=dp[i-1][j-1][1]+dp[i-1][j][2]+dp[i-1][j][3]+dp[i-1][j][4];

答案就是将所有最后列都加起来。

代码

CPP

#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N=1e3+5;
const int mod=998244353;

int n,k;

int dp[N][2*N][5];

inline void init()
{
	dp[1][1][1]=1;
	dp[1][2][2]=1;
	dp[1][2][3]=1;
	dp[1][1][4]=1;
}

signed main()
{
	cin>>n>>k;
	init();
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
//			1:X 2:X 3:. 4:.
//  		  X   .   X   .
			dp[i][j][1]+=dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][3]+dp[i-1][j-1][4];
			dp[i][j][2]+=dp[i-1][j-1][1]+dp[i-1][j][2]+dp[i-1][j-2][3]+dp[i-1][j-1][4];
			dp[i][j][3]+=dp[i-1][j-1][1]+dp[i-1][j-2][2]+dp[i-1][j][3]+dp[i-1][j-1][4];
			dp[i][j][4]+=dp[i-1][j-1][1]+dp[i-1][j][2]+dp[i-1][j][3]+dp[i-1][j][4];
			dp[i][j][1]%=mod,dp[i][j][2]%=mod,dp[i][j][3]%=mod,dp[i][j][4]%=mod;
//			cout<<i<<' '<<j<<' '<<dp[i][j][1]<<' '<<dp[i][j][2]<<' '<<dp[i][j][3]<<' '<<dp[i][j][4]<<endl;
		}
	}
	int ans=0;
	for(int i=1;i<=4;i++)
	{
		ans+=dp[n][k][i];
		ans%=mod;
	}
	cout<<ans<<endl;
    return 0;
}

题解：CF1051D Bicolorings

文章操作

代码

相关推荐

评论

题解：CF1051D Bicolorings