专栏文章

[ABC291D] Flip Cards 题解

LLANDER_TT
AT_abc291_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqyu6vd
此快照首次捕获于
2025/12/04 12:58
3 个月前
此快照最后确认于
2025/12/04 12:58
3 个月前
查看原文
csdn链接：这里

一、本题思路

本题是一个明显的dp题，考虑线性dp
令dp数组dpi,jdp_{i,j}存储方案数，其中第一维表示当前操作的卡牌编号，第二维表示当前卡牌的状态，00表示反面，11表示正面
方案数可以直接由上一个值累加而来，同时由于本题要求的是相邻的卡牌数互不相同，得出dp状态转移方程: 当bi=ai−1b_i=a_i-1时: dpi,0=dpi,0+dpi−1,1dp_{i,0}=dp_{i,0}+dp_{i-1,1}
当bi=bi−1b_i=b_i-1时: dpi,0=dpi,0+dpi−1,0dp_{i,0}=dp_{i,0}+dp_{i-1,0}
当ai=ai−1a_i=a_i-1时: dpi,1=dpi,1+dpi−1,1dp_{i,1}=dp_{i,1}+dp_{i-1,1}
当ai=bi−1a_i=b_i-1时: dpi,1=dpi,1+dpi−1,0dp_{i,1}=dp_{i,1}+dp_{i-1,0}

二、代码展示

C
#include<bits/stdc++.h>
#define int long long
#define ysq 998244353
using namespace std;
int n,a[200005],b[200005],dp[200005][2];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i]>>b[i];
	dp[1][0]=dp[1][1]=1;//初始化
	for(int i=2;i<=n;++i){
		if(b[i]!=a[i-1])dp[i][0]=(dp[i][0]+dp[i-1][1])%ysq;//状态转移方程
		if(b[i]!=b[i-1])dp[i][0]=(dp[i][0]+dp[i-1][0])%ysq;//记得加%
		if(a[i]!=a[i-1])dp[i][1]=(dp[i][1]+dp[i-1][1])%ysq;
		if(a[i]!=b[i-1])dp[i][1]=(dp[i][1]+dp[i-1][0])%ysq;
	}
	cout<<(dp[n][0]+dp[n][1])%ysq;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...