Array Without Local Maximums（codeforces1068D）计数类DP

题意：给你一个长度为n的数组a,（1<=n<=1e5 ,1<=a[i]<=200 or a[i]=-1）。a[i]=-1代表i这个位置的数是未知的否则已知，对于每个未知的数你可以把它设置成1-200之间的任意整数。问你有几种设置方法可以使得整个序列满足：a[1]<=a[2],a[n]<=a[n-1],当 2<=i<=n-1时 a[i]<=max(a[i-1],a[i+1])。答案取模998244353。

思路：问题转化一下，其实题目要求的就是你构造出来的序列里的每个数它的边上至少有一个数比它大。然后再看数据范围，每个数都在1-200之间，很容易想到用dp去做。这里需要开三维的数组来记录状态。dp[i][j][k]代表第i位数填j，k=0代表a[i]=a[i-1]的情况,k=1代表a[i]>a[i-1]的情况，k=2代表a[i]<a[i-1]的情况。

状态转移：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

dp[i][j][0]=dp[i−1][j][0/1/2],因为a[i]已经>=a[i-1]了，所以无论a[i-1]和a[i-2]什么关系都符合条件。

dp[i][j][1]= ,因为a[i-1]<a[i],所以a[i-1]与a[i-2]无论什么关系也都满足条件。

dp[i][j][2]= ,因为a[i-1]<a[i+2],所以a[i-1]就不能大于a[i-2]了。

上面的第二种状态转移显然是个前缀和，第三种状态转移显然是一个后缀和。所以可以开两个数组分别记录就好了。这样就可以做到n*k的复杂度了。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
const double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
inline ll rd() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const double eps = 1e-6;
const int M = 1e6 + 10;
const int N = 1e5 + 10;
ll dp[N][205][3];
ll pre[205], suff[205];
int a[N];
int main() {
    int n = rd();
    for (int i = 1; i <= n; i++)a[i] = rd();
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= 200; i++) {
        if (a[1] == -1 || i == a[1])dp[1][i][1] = 1;
    }
    for (int i = 1; i <= 200; i++) {
        pre[i] = pre[i - 1];
        for (int j = 0; j < 3; j++) {
            pre[i] += dp[1][i][j];
        }
    }
    for (int i = 200; i >= 1; i--) {
        suff[i] = suff[i + 1];
        for (int j = 0; j < 3; j += 2) {
            suff[i] += dp[1][i][j];
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= 200; j++) {
            if (a[i] == -1 || a[i] == j) {
                dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2]) % mod;
                dp[i][j][1] = pre[j - 1];
                dp[i][j][2] = suff[j + 1];
            }
        }
        for (int k = 1; k <= 200; k++) {
            pre[k] = pre[k - 1];
            for (int j = 0; j < 3; j++) {
                pre[k] += dp[i][k][j];
                pre[k] %= mod;
            }
        }
        for (int k = 200; k >= 1; k--) {
            suff[k] = suff[k + 1];
            for (int j = 0; j < 3; j += 2) {
                suff[k] += dp[i][k][j];
                suff[k] %= mod;
            }
        }
    }
    cout << suff[1] << endl;
}

空间优化：注意到转移的过程中,dp[i]的转移只与dp[i-1]有关系，所以可以省略掉第一维,使用滚动数组来代替

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lowbit(ll x) { return x & (-x); }
const double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
inline ll rd() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const double eps = 1e-6;
const int M = 1e6 + 10;
const int N = 1e5 + 10;
ll dp[205][3];
ll pre[205], suff[205];
int a[N];
int main() {
    int n = rd();
    for (int i = 1; i <= n; i++)a[i] = rd();
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= 200; i++) {
        if (a[1] == -1 || i == a[1])dp[i][1] = 1;
    }
    for (int i = 1; i <= 200; i++) {
        pre[i] = pre[i - 1];
        for (int j = 0; j < 3; j++) {
            pre[i] += dp[i][j];
        }
    }
    for (int i = 200; i >= 1; i--) {
        suff[i] = suff[i + 1];
        for (int j = 0; j < 3; j += 2) {
            suff[i] += dp[i][j];
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 200; j >= 1; j--) {
            if (a[i] == -1 || a[i] == j) {
                dp[j][0] = (dp[j][0] + dp[j][1] + dp[j][2]) % mod;
                dp[j][1] = pre[j - 1];
                dp[j][2] = suff[j + 1];
            }
            else {
                dp[j][0] = dp[j][1] = dp[j][2] = 0;
            }
        }
        for (int k = 1; k <= 200; k++) {
            pre[k] = pre[k - 1];
            for (int j = 0; j < 3; j++) {
                pre[k] += dp[k][j];
                pre[k] %= mod;
            }
        }
        for (int k = 200; k >= 1; k--) {
            suff[k] = suff[k + 1];
            for (int j = 0; j < 3; j += 2) {
                suff[k] += dp[k][j];
                suff[k] %= mod;
            }
        }
    }
    cout << suff[1] << endl;
}