题解：CF1067A Array Without Local Maximums

这题很显然吧。设

m=200

，对大小

[1,m]

下手即可。然后转移状态时考虑大小为

x

的可行性，若

a_i

确定强制转移即可。

这个时候我们发现转移过程有点冗余了，每次暴力

a_{i-1}

的大小转移，需要

O(nm^2)

，不妨考虑加一维表示相对大小，然后通过前缀和来优化掉冗余的转移。那么优化到

O(nm)

可过。

具体来讲，设

f_{i,j,0/1/2}

表示第

i

位大小为

j

的方案数，而

0/1/2

分别表示

a_{i-1}<a_i

、

a_{i-1}=a_i

、

a_{i-1}>a_i

。

对于状态 $0$ ，显然 $a_{i-1}$ 与 $a_{i-2}$ 大小关系如何都无所谓，因为 $a_i$ 帮助 $a_{i-1}$ 完成了限制条件，故 $f_{i,j,0}=\sum\limits^{j-1}_{k=1}f_{i-1,k,0}+f_{i-1,k,1}+f_{i-1,k,2}$ ；
对于状态 $1$ ，与状态 $0$ 一样不用考虑前者的相对大小， $f_{i,j,1}=f_{i-1,j,0}+f_{i-1,j,1}+f_{i-1,j,2}$ ；
对于状态 $2$ ，显然只能从 $1,2$ 转移过来，不然 $a_{i-1}$ 就无法满足限制条件了，故 $f_{i,j,2}=\sum\limits^m_{k=j+1}f_{i-1,k,1}+f_{i-1,k,2}$ 。

这个时候不难发现，对

f_{i-1,k,0}+f_{i-1,k,1}+f_{i-1,k,2}

做一个前缀和，对

f_{i-1,k,1}+f_{i-1,k,2}

做一个后缀和，就可以

O(m)

转移一次状态。

总体时间复杂度

O(nm)

。

评测记录 #336937092

CPP

#include <bits/stdc++.h>
#define int long long
#define lint long long
#define endl '\n'
using namespace std;
const int N = 1e5+5;
const int M = 2e2+5;
const int mod = 998244353;
 
int n,m,a[N];
int pre[M],suf[M];
int f[N][M][3];
 
inline void init(int i){
	for(int j = 1; j <= m; j++){
		pre[j] = pre[j-1] + f[i-1][j][0] + f[i-1][j][1] + f[i-1][j][2];
		pre[j] %= mod;
	}
 
	for(int j = m; j >= 1; j--){
		suf[j] = suf[j+1] + f[i-1][j][1] + f[i-1][j][2];
		suf[j] %= mod;
	}
}
 
inline void check(int i,int l,int r){
	init(i);
	
	for(int j = l; j <= r; j++){
		f[i][j][0] = pre[j-1],f[i][j][2] = suf[j+1];
		f[i][j][1] = f[i-1][j][0] + f[i-1][j][1] + f[i-1][j][2];
		f[i][j][1] %= mod;
	}
}
 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	// freopen("app.in","r",stdin);
    // freopen("app.out","w",stdout);
	
	m = 200;
 
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
 
	if(a[1] == -1)
		for(int j = 1; j <= m; j++)
			f[1][j][0] = 1;
	else f[1][a[1]][0] = 1;
 
	for(int i = 2; i <= n; i++){
		if(a[i] == -1) check(i,1,m);
		else check(i,a[i],a[i]);
	}
 
	int ans = 0;
	if(a[n] == -1){
		for(int j = 1; j <= m; j++){
			ans += f[n][j][1] + f[n][j][2];
			ans %= mod;
		}
	}else ans = (f[n][a[n]][1] + f[n][a[n]][2]) % mod;
 
	cout << ans << endl;
	return 0;
}

题解：CF1067A Array Without Local Maximums

文章操作

相关推荐

评论

题解：CF1067A Array Without Local Maximums