题解：CF2061C Kevin and Puzzle
Wide_Master
·
·
题解
题意
$n$ 个人站成一排，第 $i$ 个人会告诉你他的左边有 $a_i$ 个说谎者。
每个人有两种身份，诚实者和说谎者，诚实者一定会说真话，说谎者可能会说真话，也可能会说假话。
说谎者之间不能相邻。
现在问你游戏一共有多少种**不同的**情况。答案对 $998244353$ 取余。
## 思路
考虑动态规划，我们可以用一个数组 $dp$ 来统计答案。其中 $dp_{i,0/1}$ 用来统计第 $i$ 个人是诚实者/说谎者产生的贡献。
继续考虑初始化，我们可以初始化第 $1$ 个人的，因为他只有是诚实者或说谎者两种可能。如果他是诚实者，那么就是 $1$ 种情况，也就是说真话，即 $dp_{i,0}=1$，如果他是说谎者，那么就要判断他说的是不是真话，我们可以判断 $a_i$ 是否为 $0$，因为他左边已经没有人了。所以初始化为 $dp_{i,1}=[a_1=0]$。
接下来考虑转移方程，如果第 $i$ 个人是说谎者，那么第 $i-1$ 个人绝对不可能是说谎者，即 $dp_{i,0}\gets dp_{i-1,1}$。
如果第 $i$ 个人不是说谎者，那么就需要继续考虑。
- 第 $i-1$ 个人是说谎者。那么第 $i-2$ 个就一定不是说谎者。这需要满足 $a_i-1=a_{i-2}$，因为他们之间夹了一个说谎者。即 $dp_{i,1}=dp_{i-1,0}$。
- 第 $i-1$ 个人是诚实者。那么就需要满足 $a_i=a_{i-1}$，因为他们都是诚实者，所以不可能有差别。即 $dp_{i,1}\gets dp_{i-1,1}$。
最终的答案为 $dp_{n,0}+dp_{n,1}$。注意多测清空。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=2e5+7;
int n,a[N],dp[N][2],t;
int main()
{
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dp[1][0]=1;
if(a[1]==0)dp[1][1]=1;
else dp[1][1]=0;
for(int i=2;i<=n;i++){
dp[i][0]=dp[i-1][1];
dp[i][1]=0;
if(a[i]==a[i-1])dp[i][1]=(dp[i][1]+dp[i-1][1])%mod;
if(a[i]-1==a[i-2])dp[i][1]=(dp[i][1]+dp[i-1][0])%mod;
}
cout<<(dp[n][0]+dp[n][1])%mod<<endl;
}
return 0;
}
``````