Codeforces 1051 D.Bicolorings（DP）

Codeforces 1051 D.Bicolorings

题意：一个2×n的方格纸，用黑白给格子涂色，要求分出k个连通块，求方案数。

思路：用0,1表示黑白，则第i列可以涂00,01,10,11，（可以分别用0,1,2,3表示），于是定义dp[i][j][k]：涂到第i列分为j个连通块且第i列涂法为k的方案数，则有了代码中的转移式，共16种转移类型。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<map>

#include<queue>

#include<string>

#include<vector>

#include<cmath>

#include<climits>

#include<functional>

#include<set>

#define dd(x) cout<<#x<<" = "<<x<<" "

#define de(x) cout<<#x<<" = "<<x<<endl

#define fi first

#define se second

#define mp make_pair

#define pb push_back

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

typedef vector<int> V;

typedef map<int,int> M;

typedef queue<int> Q;

typedef priority_queue<int> BQ;

typedef priority_queue<int,vector<int>,greater<int> > SQ;

const int maxn=1e3+10,INF=0x3f3f3f3f,mod=998244353;

int dp[maxn][maxn<<1][5];//0->00, 1->01, 2->10, 3->11

inline int add(int a,int b)

{

  a+=b;

  if (a>=mod)

  	a-=mod;

  return a;

}

int main()

{

	int n,k;

	scanf("%d%d",&n,&k);

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

	for (int i=2;i<=n;++i)

	{

	  for (int j=1;j<=2*i;++j)

	  {

		dp[i][j][0]=add(dp[i][j][0],add(dp[i-1][j-1][3],add(dp[i-1][j][2],add(dp[i-1][j][1],dp[i-1][j][0]))));

		dp[i][j][1]=add(dp[i][j][1],add(dp[i-1][j-1][0],add(dp[i-1][j][1],add(j>=2?dp[i-1][j-2][2]:0,dp[i-1][j-1][3]))));

		dp[i][j][2]=add(dp[i][j][2],add(dp[i-1][j-1][0],add(dp[i-1][j][2],add(j>=2?dp[i-1][j-2][1]:0,dp[i-1][j-1][3]))));

		dp[i][j][3]=add(dp[i][j][3],add(dp[i-1][j-1][0],add(dp[i-1][j][1],add(dp[i-1][j][2],dp[i-1][j][3]))));

	  }

	}

	printf("%d",add(dp[n][k][0],add(dp[n][k][1],add(dp[n][k][2],dp[n][k][3]))));

	return 0;

}

巴特西

Codeforces 1051 D.Bicolorings（DP）

最新文章

热门文章