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

发表于 | 分类于 | | + s

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，最好用数学那种思维来推公式

#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
*/
------ 本文结束 ------