Codeforces 1051D Bicolorings 简单状压dp

72 阅读 0 评论 48 点赞

我是靠谱客的博主土豪乐曲，这篇文章主要介绍Codeforces 1051D Bicolorings 简单状压dp，现在分享给大家，希望可以做个参考。

文章目录

- 题意
- 题解

题意

给一个2*n的网格涂黑白两色,求涂出k个连通块的方法总数膜998244353.

题解

可以作为状压dp的入门题.
由于连通块构成需要相邻,只有上一列的两个格子的颜色对这一列构成连通块的个数有影响.
两个格子的颜色的情况只有4种可能,可以状压这两个格子的涂色方法.
用dp[i][j][k]表示当前涂到 $i$ 列,有 $j$ 个连通块,上一列的状态是 $k$ 的时候的方案总数.
利用当前列的状态和上一列状态的关系推断会增加几个连通块,并进行状态的转移.

复制代码

#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int u=0,dp=1;char c=gc();
  for (;!isdigit(c);c=gc()) dp^=c=='-';
  for (;isdigit(c);c=gc()) u=(u<<3)+(u<<1)+(c^'0');
  return dp?u:-u;
  }
template <typename mitsuha>
inline bool read(mitsuha &u){
  u=0;int dp=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) dp^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) u=(u<<3)+(u<<1)+(c^'0');
  return u=dp?u:-u,1;
  }
template <typename mitsuha>
inline int write(mitsuha u){
  if (!u) return 0&pc(48);
  if (u<0) u=-u,pc('-');
  int bit[20],i,p=0;
  for (;u;u/=10) bit[++p]=u%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int aoi=1018,mod=998244353;
ll dp[aoi][aoi<<1][4]; 
/*dp[i][j][k]表示涂到第i列,有j个连通块,上一列涂的状态是k的方法总数.*/

int main(){
int i,j,n=read(),k=read();
dp[1][1][0]=dp[1][2][1]=dp[1][2][2]=dp[1][1][3]=1; // 初始化涂同一种颜色1个块,不同颜色两个块.
for (i=2;i<=n;++i){
  for (j=1;j<=2*i;++j){
    dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j-1][3])%mod;
    dp[i][j][1]=(dp[i-1][j-1][0]+dp[i-1][j][1]+(j>1?dp[i-1][j-2][2]:0)+dp[i-1][j-1][3])%mod;
    dp[i][j][2]=(dp[i-1][j-1][0]+(j>1?dp[i-1][j-2][1]:0)+dp[i-1][j][2]+dp[i-1][j-1][3])%mod;
	dp[i][j][3]=(dp[i-1][j-1][0]+dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][3])%mod;
	}
  }
for (i=0;i<4;++i) ***dp=(***dp+dp[n][k][i])%mod;
write(***dp);  //  我直接用dp[0][0][0]代替ans,答案就是dp[n][k][0-3]的和.
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int u=0,dp=1;char c=gc();
  for (;!isdigit(c);c=gc()) dp^=c=='-';
  for (;isdigit(c);c=gc()) u=(u<<3)+(u<<1)+(c^'0');
  return dp?u:-u;
  }
template <typename mitsuha>
inline bool read(mitsuha &u){
  u=0;int dp=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) dp^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) u=(u<<3)+(u<<1)+(c^'0');
  return u=dp?u:-u,1;
  }
template <typename mitsuha>
inline int write(mitsuha u){
  if (!u) return 0&pc(48);
  if (u<0) u=-u,pc('-');
  int bit[20],i,p=0;
  for (;u;u/=10) bit[++p]=u%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int aoi=1018,mod=998244353;
ll dp[aoi][aoi<<1][4]; 
/*dp[i][j][k]表示涂到第i列,有j个连通块,上一列涂的状态是k的方法总数.*/

int main(){
int i,j,n=read(),k=read();
dp[1][1][0]=dp[1][2][1]=dp[1][2][2]=dp[1][1][3]=1; // 初始化涂同一种颜色1个块,不同颜色两个块.
for (i=2;i<=n;++i){
  for (j=1;j<=2*i;++j){
    dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j-1][3])%mod;
    dp[i][j][1]=(dp[i-1][j-1][0]+dp[i-1][j][1]+(j>1?dp[i-1][j-2][2]:0)+dp[i-1][j-1][3])%mod;
    dp[i][j][2]=(dp[i-1][j-1][0]+(j>1?dp[i-1][j-2][1]:0)+dp[i-1][j][2]+dp[i-1][j-1][3])%mod;
	dp[i][j][3]=(dp[i-1][j-1][0]+dp[i-1][j][1]+dp[i-1][j][2]+dp[i-1][j][3])%mod;
	}
  }
for (i=0;i<4;++i) ***dp=(***dp+dp[n][k][i])%mod;
write(***dp);  //  我直接用dp[0][0][0]代替ans,答案就是dp[n][k][0-3]的和.
}