「Codeforces 1067A」Array Without Local Maximums
题目传送门
题意
给定长度为 \(n\) 的序列 \(a\)，有些位置是 \(-1\)，其余位置是 \(1\) 到 \(200\) 的一个整数。你需要在 \(-1\) 的位置填上\(1\) 到 \(200\) 的一个整数，使得序列 \(a\) 是好的。一个序列 \(a\) 是好的当且仅当满足以下三个条件：
- \(a_1\le a_2\)
- \(a_n\le a_{n-1}\)
- \(\forall i\in [2,n-1],a_i\le \max(a_{i-1},a_{i+1})\)
求方案数 \(\bmod 998244353\) 的值。
\(n\le 10^5\)
题解
考虑 DP，\(dp_{i,j,0/1}\) 表示前 \(i\) 个数，\(a_i\) 为 \(j\)，\(a_{i-1}< a_i\) / \(a_{i-1}\ge a_i\) 时的方案数。有转移
\[\begin{aligned} dp_{i,j,0}&=\sum_{k=1}^{j-1} dp_{i-1,k,0}+dp_{i-1,k,1}\\ dp_{i,j,1}&=dp_{i-1,j,0}+\sum_{k=j}^{200} dp_{i-1,k,1}\end{aligned}\]
可以发现这个式子可以用前缀和优化。
时间复杂度 \(O(nm)\)，其中 \(m=200\)。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <cstdio>
#include <cctype>
int read(){
register int x = 0;
register char f = 1, ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = !f;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return f ? x : -x;
}
#define N 100005
#define P 998244353
int n, a[N], dp[N][205][2], pre[N][205][2];
int add(int x, int y){
return (x += y) >= P ? x - P : x;
}
int del(int x, int y){
return (x -= y) < 0 ? x + P : x;
}
int suf(int i, int j, int k){
return del(pre[i][200][k], pre[i][j - 1][k]);
}
int main(){
n = read();
for (register int i = 1; i <= n; ++i) a[i] = read();
for (register int i = 1; i <= 200; ++i){
if (a[1] == -1 || i == a[1]) dp[1][i][0] = 1;
pre[1][i][0] = add(pre[1][i - 1][0], dp[1][i][0]);
}
for (register int i = 2; i <= n; ++i)
for (register int j = 1; j <= 200; ++j){
if (a[i] == -1 || a[i] == j){
dp[i][j][0] = add(pre[i - 1][j - 1][0], pre[i - 1][j - 1][1]);
dp[i][j][1] = add(dp[i - 1][j][0], suf(i - 1, j, 1));
}
pre[i][j][0] = add(pre[i][j - 1][0], dp[i][j][0]);
pre[i][j][1] = add(pre[i][j - 1][1], dp[i][j][1]);
}
printf("%d\n", pre[n][200][1]);
}
|
