题解：CF2144C Non-Descending Arrays

· · 题解

思路：

你考虑本题的转化：对于每一位置上的点，可以交换当且仅当前面序列合法，发现具有最优结构，想一想 dp 做法。

思考如何转移，画个图（样例四）:


可以发现，实际上就是求从最左边走到最右边的路径条数。

那么对于每个点记录一个 dp 值为可以到该点的路径数量，从左向右转移即可。

代码：

/*

*/
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
#define INF 1e18
#define lb long double
#define ls (id<<1)
#define rs (id<<1|1)
#define rep(i,l,r,k) for(int i=(l);i<=(r);i+=(k))
#define dep(i,r,l,k) for(int i=(r);i>=(l);i-=(k))
#define mk(a,b) make_pair(a,b)
#define me(a,b) memset(a,b,sizeof(a))
#define pb(x) push_back(x)
#define pr putchar
#define fi first
#define se second
#define max(a,b)((a)>(b)?(a):(b))
#define min(a,b)((a)<(b)?(a):(b))
using namespace std;
random_device rd;
unsigned int seed=rd();
mt19937 Rand(seed);
typedef pair<int,int> pii;
const int M=2e5+110,mod=1e9+7,Mod=998244353;
__gnu_pbds::gp_hash_table<string,int>ml;
inline int read(){int sum=0,k=1;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')k=-1;c=getchar();
    }while(c>='0'&&c<='9'){sum=sum*10+c-48;c=getchar();
    }return sum*k;
}inline void wr(int x){if(x<0) putchar('-'),x=-x;
    if(x>9) wr(x/10);return void(putchar(x%10+'0'));}
int T=read(),n,a[M],b[M],dp[M][2];//开了二维代替
signed main(){
    while(T--){
        n=read();//读入
        rep(i,1,n,1) a[i]=read();rep(i,1,n,1) b[i]=read();
        dp[1][0]=dp[1][1]=1;//初始化
        rep(i,2,n,1){
            dp[i][0]=dp[i][1]=0;//初始化
            //发现转移是对称的,可以自己推一下
            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]=dp[i][0]%Mod,dp[i][1]=dp[i][1]%Mod;
        }
        //输出两个终点的路径答案之和
        cout<<(dp[n][0]+dp[n][1])%Mod<<'\n';
    }
    return 0;
}
/*
3
3
2 1 4
1 3 2
1
4
4
5
2 3 3 4 4
1 1 3 5 6

*/