题解：CF2144C Non-Descending Arrays

解题思路

简单 DP 题（甚至可能不算 DP），提供一种容易理解并且好写的做法，复杂度

O(n)

。

容易想到设 $f_i$ 表示只考虑下标小于等于 $i$ 的 $a,b$ 数组的方案数。

然后考虑转移，我们不妨假定前

i-1

个元素已经非递减了。当

a_i\ge a_{i-1}

并且

a_i\ge b_{i-1}

时，

a_i

换不换均满足条件。同理，当

b_i

同时满足

b_i\ge a_{i-1}

和

b_i \ge b_{i-1}

时，那么

b_i

换或不换也满足条件。如此那么对于下标

i

，我们有换或不换两种方案，转移方程式为：

f_i=2f_{i-1}(a_i\ge a_{i-1},a_i\ge b_{i-1},b_i\ge a_{i-1},b_i \ge b_{i-1})

但如果

a_i

或

b_i

至少有一个并不是两个条件都满足，就只有一种选择，不会产生贡献。因为题目保证了“there is at least one good subset”，所以不会存在

a_i

或

b_i

两个条件都不满足的情况。

代码

不开 long long 见祖宗。

CPP

123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>
using namespace std;
const int N=1002,M=1002,mod=998244353;
#define A (a[i]>=a[i-1])
#define B (b[i]>=b[i-1])
#define C (a[i]>=b[i-1])
#define D (b[i]>=a[i-1])
int T,n,a[N],b[N];
long long f[N];
//bool c[N];

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++){
			scanf("%d",&b[i]);
			f[i]=0;//,c[i]=false;
		}
		f[1]=2;//,c[1]=true;
		for(int i=2;i<=n;i++){
			int x=0;
			x=(A&&B?1:0)+(C&&D?1:0);
			f[i]=(f[i-1]*x)%mod;
		}
		printf("%lld\n",f[n]);
	}
	return 0;
}

没用的小优化

发现

f_i

仅有的一维

i

可以滚动掉，将数组

f_i

优化为一个变量。

代码

不开 long long 见祖宗。

CPP

1234567891011121314151617181920#include<bits/stdc++.h>
using namespace std;
const int N=1002,mod=998244353;
int T,n,a[N],b[N];
long long ans;

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=n;i++) scanf("%d",&b[i]);
		ans=2;
		for(int i=2;i<=n;i++)
			if(a[i]>=a[i-1]&&b[i]>=b[i-1]&&a[i]>=b[i-1]&&b[i]>=a[i-1])
				(ans<<=1)%=mod;
		printf("%lld\n",ans);
	}
	return 0;
}

题解：CF2144C Non-Descending Arrays

文章操作

解题思路

没用的小优化

相关推荐

评论

题解：CF2144C Non-Descending Arrays