posted on 2022-08-15 00:08:56 | under 题解 | source
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;
}