题解：CF1067A Array Without Local Maximums

akakal · 2025-09-05 10:39:16 · 题解

这题很显然吧。设 m=200，对大小 [1,m] 下手即可。然后转移状态时考虑大小为 x 的可行性，若 a_i 确定强制转移即可。

这个时候我们发现转移过程有点冗余了，每次暴力 a_{i-1} 的大小转移，需要 O(nm^2)，不妨考虑加一维表示相对大小，然后通过前缀和来优化掉冗余的转移。那么优化到 O(nm) 可过。

具体来讲，设 f_{i,j,0/1/2} 表示第 i 位大小为 j 的方案数，而 0/1/2 分别表示 a_{i-1}<a_i、a_{i-1}=a_i、a_{i-1}>a_i。

• 对于状态 0，显然 a_{i-1} 与 a_{i-2} 大小关系如何都无所谓，因为 a_i 帮助 a_{i-1} 完成了限制条件，故 f_{i,j,0}=\sum\limits^{j-1}_{k=1}f_{i-1,k,0}+f_{i-1,k,1}+f_{i-1,k,2}；
• 对于状态 1，与状态 0 一样不用考虑前者的相对大小，f_{i,j,1}=f_{i-1,j,0}+f_{i-1,j,1}+f_{i-1,j,2}；
• 对于状态 2，显然只能从 1,2 转移过来，不然 a_{i-1} 就无法满足限制条件了，故 f_{i,j,2}=\sum\limits^m_{k=j+1}f_{i-1,k,1}+f_{i-1,k,2}。

这个时候不难发现，对 f_{i-1,k,0}+f_{i-1,k,1}+f_{i-1,k,2} 做一个前缀和，对 f_{i-1,k,1}+f_{i-1,k,2} 做一个后缀和，就可以 O(m) 转移一次状态。

总体时间复杂度 O(nm)。

评测记录 #336937092

#include <bits/stdc++.h>
#define int long long
#define lint long long
#define endl '\n'
using namespace std;
const int N = 1e5+5;
const int M = 2e2+5;
const int mod = 998244353;

int n,m,a[N];
int pre[M],suf[M];
int f[N][M][3];

inline void init(int i){
    for(int j = 1; j <= m; j++){
        pre[j] = pre[j-1] + f[i-1][j][0] + f[i-1][j][1] + f[i-1][j][2];
        pre[j] %= mod;
    }

    for(int j = m; j >= 1; j--){
        suf[j] = suf[j+1] + f[i-1][j][1] + f[i-1][j][2];
        suf[j] %= mod;
    }
}

inline void check(int i,int l,int r){
    init(i);

    for(int j = l; j <= r; j++){
        f[i][j][0] = pre[j-1],f[i][j][2] = suf[j+1];
        f[i][j][1] = f[i-1][j][0] + f[i-1][j][1] + f[i-1][j][2];
        f[i][j][1] %= mod;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // freopen("app.in","r",stdin);
    // freopen("app.out","w",stdout);

    m = 200;

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    if(a[1] == -1)
        for(int j = 1; j <= m; j++)
            f[1][j][0] = 1;
    else f[1][a[1]][0] = 1;

    for(int i = 2; i <= n; i++){
        if(a[i] == -1) check(i,1,m);
        else check(i,a[i],a[i]);
    }

    int ans = 0;
    if(a[n] == -1){
        for(int j = 1; j <= m; j++){
            ans += f[n][j][1] + f[n][j][2];
            ans %= mod;
        }
    }else ans = (f[n][a[n]][1] + f[n][a[n]][2]) % mod;

    cout << ans << endl;
    return 0;
}