Array Without Local Maximums

Created by LXC on Thu Jul 27 09:38:49 2023

https://codeforces.com/problemset/problem/1067/A

ranting: 1900

tag: dp

problem

给出n个数的数组a，每个数的大小在1到200或者为-1，你需要所有将-1替换为1到200内的数，形成一个新的数组，这个数组满足任意元素a[i]必定小于等于它的一个相邻元素a[i-1]或a[i+1]。

问有多少种这样的新数组。

$2 \le n\le 10^5$

solution

朴素做法就是枚举每个-1的可能再判断是否满足条件，如果每个数都是-1，那么每个-1有200种可能性，构造数组的个数有$200^n$个，判断每个数组合法所需时间为$O(n)$，总时间复杂度为$O(n\cdot200^n)$

考虑动态规划，

观察相邻前缀数组之间合法数组的个数是否存在子问题的关系。

合法数组的相邻元素存在大小关系的条件，我们可以在前缀状态种加入相邻元素的大小关系的参数。每个-1有200种可能，我们可以定义$f_{i,j,k}$为以k结尾$a_{i-1}$与$a_{i}$的大小关系为j（j=0，小于，j=1，大于等于）前i个数的合法数目。

$a_{i-1} < a_i$，则$a_{i-2}$与$a_{i-1}$关系可以是任意的。
所以$f_{i,0,k} = \sum \limits_{c=1}^{k-1} (f_{i-1, 0, c} + f_{i-1, 1, c})$

$a_{i-1} \ge a_i$，则$a_{i-2} \ge a_{i-1}$才能保证$a_{i-1}$合法，但是还有一种特殊情况，$a_{i-1} = a_i$时，可以存在$a_{i-2} < a_{i-1}$。
所以$f_{i,1,k} = \sum \limits_{c=k}^{200} (f_{i-1, 0, c} + f_{i-1, 1, c}) + f_{i-1, 0, k}$

每次转移时预处理前/后缀数组，可以将$O(g^2n)$将为$O(gn)$，$g=200$。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 100005
#define MOD 998244353
using namespace std;

// f[i][j][k] 前i个以k结尾，a[i-1]和a[i]的大小关系为j的方案数。0 小于 1大于等于
int f[N][2][202];
int a[N];

void sol() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    if (a[1] != -1 && a[2] != -1) {
        if (a[1] > a[2]) {
            cout << "0\n";
            return;
        }
        if (a[1] == a[2]) {
            f[2][1][a[2]] = 1;
        } else {
            f[2][0][a[2]] = 1;
        }
    } else if (a[1] != -1 && a[2] == -1) {
        f[2][1][a[1]] = 1;
        for (int i = a[1] + 1; i <= 200; i++) {
            f[2][0][i] = 1;
        }
    } else if (a[1] == -1 && a[2] != -1) {
        f[2][1][a[2]] = 1;
        // for (int i = 1; i < a[2]; i++) {
        //     f[2][0][a[2]]++;
        // }
        f[2][0][a[2]] = a[2] - 1;
    } else {
        for (int i = 1; i <= 200; i++) {
            f[2][1][i] = 1;
            f[2][0][i] = i - 1;
        }
    }
    for (int i = 3; i <= n; i++) {
        vector<vector<ll>> prf(2, vector<ll>(202, 0)),
            suf(2, vector<ll>(202, 0));
        for (int j = 0; j < 2; j++) {
            for (int k = 1; k <= 200; k++) {
                prf[j][k] = (prf[j][k - 1] + f[i - 1][j][k]) % MOD;
                prf[j][k] %= MOD;
            }
            for (int k = 200; k >= 1; k--) {
                suf[j][k] = (suf[j][k + 1] + f[i - 1][j][k]) % MOD;
                suf[j][k] %= MOD;
            }
        }
        if (a[i] == -1) {
            for (int j = 1; j <= 200; j++) {
                f[i][0][j] = (prf[0][j - 1] + prf[1][j - 1]) % MOD;
                f[i][0][j] %= MOD;
                f[i][1][j] = (suf[1][j] + f[i - 1][0][j]) % MOD;
                f[i][1][j] %= MOD;
            }
        } else {
            int j = a[i];
            f[i][0][j] = (prf[0][j - 1] + prf[1][j - 1]) % MOD;
            f[i][0][j] %= MOD;
            f[i][1][j] = (suf[1][j] + f[i - 1][0][j]) % MOD;
            f[i][1][j] %= MOD;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= 200; i++) {
        ans += f[n][1][i];
        ans %= MOD;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}