CF2144C Non-Descending Arrays 题解

思路

我们设

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

CPP

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

CF2144C Non-Descending Arrays 题解

文章操作

相关推荐

评论

CF2144C Non-Descending Arrays 题解