题解：CF2144C Non-Descending Arrays
zsjaaaxy
·
·
题解
思路
注意到每一位下标只有换和不换两种状态，考虑动态规划，将换或不换压入数组的一维使其满足无后效性。
可以用 f_{i,1} 表示处理到第 i 位时选择换有几种方案；
转移时类似加法原理。
进行状态转移时要判断是否能够成立。
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
long long t,n,a[1000],b[1000],dp[1000][2];
const long long mod=998244353;
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
for(int i=1;i<=n;i++)
{
dp[i][0]=dp[i][1]=0;
}
dp[0][0]=dp[0][1]=1;
for(int i=1;i<=n;i++)
{
//分类讨论转移方程
if(a[i]>=a[i-1]&&b[i]>=b[i-1])
{
dp[i][0]+=dp[i-1][0];
dp[i][1]+=dp[i-1][1];
}
if(a[i]>=b[i-1]&&b[i]>=a[i-1])
{
dp[i][0]+=dp[i-1][1];
dp[i][1]+=dp[i-1][0];
}
dp[i][0]%=mod,dp[i][1]%=mod;
}
cout<<(dp[n][0]+dp[n][1])/2<<"\n";
}
return 0;
}
```
# 后记
注意代码最后输出答案时除二是应为 $dp_{1,1}$ 与 $dp_{1,0}$ 均为 $2$ ，但实际上应为 $1$ 。