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;
}
一些关于这个题的思考
考场上得出了 \(L_i\leq l_i\leq r_i\leq R_i\) 的结论，然后往区间 DP 上面想了，最后不想写代码了。
在手推的时候，我发现了一些性质：
- 对于任意 \([L_i,R_i]\)，它们要么完全包含，要么没有交集。
- 所有 \([L_i,R_i]\) 可以构成一棵有包含关系的树。\(P_i<P_{fa_i}\)。
- 对于树上一个区间，它的子节点加上这个区间原来在的编号，刚好完全覆盖这个区间。
于是，做法是，在这棵树上 dfs，算出这个区间的前后缀 DP 值，滚动更新一下。但是没写出来，可能是假的。但是这个树是有价值的。
struct node{
int x,id,l,r;
node(int x=0,int id=0,int l=0,int r=0):x(x),id(id),l(l),r(r){}
bool operator<(node b){return x>b.x;}
};
bool cmp(node a,node b){return a.l<b.l;}
int n;
node a[5010];
vector<node> g[5010];
int get(int i,int d){
for(int j=i;0<=j&&j<=n+1;j+=d){
if(a[j].x>a[i].x) return j-d;
}
return -114514;
}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i;
a[0].x=a[n+1].x=1e9;
for(int i=1;i<=n;i++) a[i].l=get(i,-1),a[i].r=get(i,1);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[j].l<=a[i].l&&a[i].r<=a[j].r){
g[j].push_back(a[i]);
break;
}
}
}
for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end(),cmp);
printf("%lld\n",dfs(1).f.back());
return 0;
}