题解 AGC058B 【Adjacent Chmax】

· · 题解

problem

一个长为 n 的排列 P，每次可以选择一个 i，令 v=\max(P_i,P_{i+1})，使 P_i=P_{i+1}=v，求若干次操作后有多少种不同的序列。1\leq n\leq 5000。

solution

显然地，对于一个 P_i，它要么被完全覆盖，要么会占领一段区间 [l_i,r_i]。显然这些 [l_i,r_i] 要连续，它占领的这一段区间是由这个最大值扩散出去的，所以不能扩散到比它大的值。令它能扩散的区域是 [L_i,R_i]（这部分暴力），显然 L_i\leq l_i\leq r_i\leq R_i（这里注意 i 号点最终不一定会被它自己覆盖）。于是 DP，设 f_{i,j} 表示当 r_i=j 时的方案数，枚举 l_i 在哪里，从 f_{i-1,l_i-1} 转移就可以了。

code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int P=998244353;
int n,a[5010];
LL f[5010][5010];
int main(){
//  #ifdef LOCAL
//      freopen("input.in","r",stdin);
//  #endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    a[0]=a[n+1]=1e9;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        int l=i,r=i;
        while(l>=1&&a[l-1]<=a[i]) l--;
        while(r<=n&&a[r+1]<=a[i]) r++;
        memcpy(f[i],f[i-1],sizeof f[i]);
        LL sum=f[i][l-1]; 
        for(int j=l;j<=r;j++){
            f[i][j]=(f[i][j]+sum)%P;
            sum=(sum+f[i-1][j])%P;
        }
    }
    printf("%lld\n",f[n][n]);
    return 0;
}

一些关于这个题的思考