题解：AT_agc058_b [AGC058B] Adjacent Chmax

· · 题解

Solution

把操作视为染色。那么一个数能染到的区间是 [L_i,R_i]，其中 L_i,R_i 分别表示左边和右边最后一个不超过 p_i 的位置。

从 p_1 \sim p_n 依次加入颜色，每个时刻能染到的位置都是一段前缀，因为能染到的任意一个位置都是由目前考虑的这些颜色中的某一个扩展出去的连续区间。所以设 f_{i,j} 表示用了 p _{1 \sim i}，染色了 [1,j] 的方案数，初始时 f_{0,0}=1。

对于 f_{i,j}，我们如果不染色，那么它的颜色就必须是之前染的，所以 f_{i,j}=f_{i-1,j}。如果染色，需要满足 L_i \le j \le R_i，考虑这部分的转移：对于 j \le i 的部分，我们要让 j 染成 p_i，染的是 [j,i] 这一段，对左边没有限制，所以方案数是 f_{i,j-1}。对于 j>i 的部分，我们要求 [i,j] 必须进行染色，这样才能染成 p_i。考虑 f_{i-1,j} 给 j 染上的颜色一定比 p_i 大，不然无法跨过 i 这个位置，因此 f_{i,j-1} 存储的方案有两部分，第一种为 j-1 染成 p_i 的方案，第二部分是将 j-1 染成某个比 p_i 大的颜色的方案。我们只需要先染 [j,i] 再染之前的方案就能做到 j 的颜色为 p_i，所以 j>i 部分的方案也是 f_{i,j-1}。这是足够的，因为如果染了 j 那么 [i,j] 中的颜色不可能比 p_i 小。

更好理解的方式是枚举 p_i 染的范围，即 f_{i,j}=\sum_{k=L_i-1}^j f_{i-1,k}，然后前缀和优化，直接做在 f 上。

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
typedef long long ll;
namespace FastIO{
    template<typename T=int> T read(){
        T x=0;int f=1;char c=getchar();
        while(!isdigit(c)){if(c=='-') f=~f+1;c=getchar();}
        while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
        return x*f;
    }
    template<typename T> void write(T x){
        if(x<0){putchar('-');x=-x;}
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }
    template<typename T> void Write(T x,char c='\n'){write(x);putchar(c);}
}
using namespace FastIO;
const int MOD=998244353;
const int maxn=5005;
int f[maxn][maxn],a[maxn];
int main(){
    int n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    f[0][0]=1;a[0]=a[n+1]=n+1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++) f[i][j]=f[i-1][j];
        int L=i,R=i;
        while(a[L]<=a[i]) L--;
        while(a[R]<=a[i]) R++;
        for(int j=L+1;j<R;j++) f[i][j]=(f[i][j]+f[i][j-1])%MOD;
    }
    write(f[n][n]);
    return 0;
}