CF2144C Non-Descending Arrays 题解

KamLam · 2025-09-16 09:07:43 · 题解

思路

我们设 dp_{i,j} 为处理到第 i 个位置时选择状态 j（0 即不交换，1 即交换）的方案数。

对于每个 i (i \geq 2)，枚举当前状态 k \in [0,1] 和前一个状态 j \in [0,1]：

定义前一个位置 i-1 在状态 j 下的两个值，若 j=0 则为 (a_{i-1}, b_{i-1})，若 j=1 则为 (b_{i-1}, a_{i-1})，记为 aj,bj；定义当前位置 i 在状态 k 下的两个值，若 k=0 则为 (a_i, b_i)，若 k=1 则为 (b_i, a_i)，记为 ak,bk。

如果 aj\leq ak 且 bj\leq bk，那么我们把 dp_{i,k} 加上 dp_{i-1,j}。

最后输出 dp_{n,0}+dp_{n,1} 即可。

时间复杂度：O(n)。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100+5,MOD=998244353;
int T,n;
int a[N],b[N];
int dp[N][2];
int main()
{
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        dp[1][0]=dp[1][1]=1;
        for(int i=2;i<=n;i++)
            for(int j=0;j<2;j++)
            {
                int ja=(!j?a[i-1]:b[i-1]);
                int jb=(!j?a[i-1]:b[i-1]);
                for(int k=0;k<2;k++)
                {
                    int ka=(!k?a[i]:b[i]);
                    int kb=(!k?b[i]:a[i]);
                    if(ja<=ka&&jb<=kb)dp[i][k]=(dp[i][k]+dp[i-1][j])%MOD;
                }
            }
        cout<<(dp[n][0]+dp[n][1])%MOD<<'\n';
    }
    return 0;
}