[ABC291D] Flip Cards 题解

· · 题解

csdn链接：这里

一、本题思路

本题是一个明显的dp题，考虑线性dp

令dp数组dp_{i,j}存储方案数，其中第一维表示当前操作的卡牌编号，第二维表示当前卡牌的状态，0表示反面，1表示正面

方案数可以直接由上一个值累加而来，同时由于本题要求的是相邻的卡牌数互不相同，得出dp状态转移方程: 当b_i=a_i-1时:

dp_{i,0}=dp_{i,0}+dp_{i-1,1}

当b_i=b_i-1时:

dp_{i,0}=dp_{i,0}+dp_{i-1,0}

当a_i=a_i-1时:

dp_{i,1}=dp_{i,1}+dp_{i-1,1}

当a_i=b_i-1时:

dp_{i,1}=dp_{i,1}+dp_{i-1,0}

二、代码展示

#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;
}