Codeforces 1051 D.Bicolorings(DP)
发布时间:2020-12-14 04:20:03 所属栏目:大数据 来源:网络整理
导读: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的方案
Codeforces 1051 D.Bicolorings #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(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(j>=2?dp[i-1][j-2][1]:0,dp[i-1][j-1][3])))); dp[i][j][3]=add(dp[i][j][3],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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容