Codeforces 1068D(DP+前缀和优化)

Codeforces 1068E
题意:有一个长度为$n$的序列,满足对于所有的$a_x$, 与它相邻的两个元素$a_{x-1}$和$a_{x+1}$中至少有一 一个大于等于它,其中$a_1$和$a_n$当然只有一 个相邻元素,现在这个序列中有些数字被破坏了(标记为$-1$) ,问有多少种合法恢复方案(每个数字$∈[1,200]$)

计数统计方案问题 DP 没跑了。
数据范围可以看出DP状态是$O(200n)$级别,我们设$dp(i,j)$为前$i$个数第$i$个数填$j$的方案数。
发现无法处理满足条件。我们加一维 0/1 表示当前$i$不满足条件/满足条件。然后分情况讨论:
现在在$(i, j)$
1、从$dp(i-1,k,0)$转移:
(1) 当$k < j$时,$dp(i,j,0)=\sum dp(i-1,k,0)$
(2) 当$k > j$时,无满足情况
(3) 当$k=j$时,$dp(i,j,1)+=dp(i-1,j,0)$
2、从$dp(i-1,k,1)$转移:
(1) 当$k < j$时,$dp(i,j,0)=\sum dp(i-1,k,1)$
(2) 当$k > j$时,$dp(i,j,1)=\sum dp(i-1,k,1)$
(3) 当$k=j$时,$dp(i,j,1)+=dp(i-1,j,1)$
上面可以画简图来理解。和CF 1013E类似。

然后预处理$i=1$的值作为初值。
对于这些求和,可以用前缀和后缀和优化。

知识点:
1、大分类讨论DP,最好用数学那种思维来推公式

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 998244353;
const int MAXN = 100000 + 5;
int n, ai[MAXN];
LL dp[3][205][3], pre[205], suf[205];
void clean() {
ms(suf, 0), ms(pre, 0), ms(dp, 0);
}
int solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &ai[i]);
clean();
int cur = 1;
if (ai[1] != -1) dp[cur ^ 1][ai[1]][0] = 1; else for (int i = 1; i <= 200; ++i) dp[cur ^ 1][i][0] = 1;
pre[0] = suf[201] = 0;
for (int i = 1; i <= 200; ++i) pre[i] = (pre[i - 1] + (dp[cur ^ 1][i][0] + dp[cur ^ 1][i][1]) % MO) % MO;
for (int i = 200; i >= 1; --i) suf[i] = (suf[i + 1] + dp[cur ^ 1][i][1]) % MO;
for (int i = 2; i <= n; ++i) {
if (ai[i] == -1) {
for (int j = 1; j <= 200; ++j) {
dp[cur][j][0] = pre[j - 1];
dp[cur][j][1] = suf[j + 1];
dp[cur][j][1] = (dp[cur][j][1] + dp[cur ^ 1][j][1]) % MO;
dp[cur][j][1] = (dp[cur][j][1] + dp[cur ^ 1][j][0]) % MO;
}
} else {
dp[cur][ai[i]][0] = pre[ai[i] - 1];
dp[cur][ai[i]][1] = suf[ai[i] + 1];
dp[cur][ai[i]][1] = (dp[cur][ai[i]][1] + dp[cur ^ 1][ai[i]][1]) % MO;
dp[cur][ai[i]][1] = (dp[cur][ai[i]][1] + dp[cur ^ 1][ai[i]][0]) % MO;
}
cur ^= 1;
pre[0] = suf[201] = 0;
for (int j = 1; j <= 200; ++j) pre[j] = (pre[j - 1] + (dp[cur ^ 1][j][0] + dp[cur ^ 1][j][1]) % MO) % MO;
for (int j = 200; j >= 1; --j) suf[j] = (suf[j + 1] + dp[cur ^ 1][j][1]) % MO;
for (int j = 1; j <= 200; ++j) dp[cur][j][0] = dp[cur][j][1] = 0;
}
LL ans = 0;
if (ai[n] != -1) cout << dp[cur ^ 1][ai[n]][1]; else {
for (int i = 1; i <= 200; ++i) ans = (ans + dp[cur ^ 1][i][1]) % MO;
cout << ans;
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
3
-1 2 2
*/

------ 本文结束 ------