题目概述

AtCoder Regular Contest 104F

解题报告

我又来翻译题解了😭。

我们在最前面加上一个 $+\infty$ ，然后把 $P$ 中的 $-1$ 改成 $0$ ，那么不难发现 $P_i\to i$ 连边构成了一棵树。

这棵树有一个重要性质：一棵子树一定是由连续的一段下标 $[L,R]$ 构成的，且这颗子树的根为 $L$ 。

把 $P_i\to i$ 当作一条线段 $(P_i,i)$ ，只要证明这样的线段不可能相交，就可以说明子树是连续的一段了：假设 $(P_i,i)$ 和 $(P_j,i)$ 相交（ $P_i<P_j<i<j$ ），那么 $H_{i}\ge H_{P_j}$ ，但是 $H_i\ge H_{P_j}$ 时，$j$ 是不可能连向 $P_j$ 的，与假设矛盾。

显然一棵树对应了一个 $\{P\}$ ，所以我们可以枚举树，然后判断这棵树是否满足 $\{X\}$ 的限制。判断方式使用贪心：一个点 $H$ 的最小值是 $\max\{$ 子树中 $H$ 最大值 $+1$ , 编号较小的同层点的 $H$ 最大值 $\}$ ，所有点的 $H$ 小于等于 $X$ 时则符合限制。

因此我们可以考虑DP：定义 $f_{L,R,x}$ 表示 $[L,R]$ 中构成的森林中 $H$ 最大值为 $x$ 时的方案数，$g_{L,R,x}$ 表示 $[L,R]$ 中构成的树（显然 $L$ 是根）中 $H$ 最大值为 $x$ 时的方案数。

$$ g_{L,R,x}=f_{L+1,R,x-1}(x\le X_L)\\ f_{L,R,x}=g_{L,R,x}+\sum_{i=L}^{R-1}\sum_{j=1}^{x}f_{L,i,j}g_{i+1,R,x}+[x\le X_{i+1}]\sum_{i=L}^{R-1}\sum_{j=1}^{x-1}f_{L,i,x}g_{i+1,R,j} $$

为什么要分别定义森林和树？这是个经典去重方法：强制第一棵树不同，其他随意。

转移 $f$ 时，要么左边的森林最大值为 $x$ ，要么右边的树最大值为 $x$ 。但是要注意左边森林最大值为 $x$ 时，一定要满足 $x\le X_{i+1}$ 才能转移（因为即使右边的树 $H$ 达不到 $x$ ，也必须强行修改成 $x$ ）。

前缀和优化一下，复杂度 $O(n^4)$ ，最后的答案为 $\sum_if_{1,n,i}$ 。

题目概述

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100,MOD=1e9+7;

int n,a[maxn+5],ans;bool vis[maxn+5][maxn+5];
int f[maxn+5][maxn+5][maxn+5],g[maxn+5][maxn+5][maxn+5];
int sf[maxn+5][maxn+5][maxn+5],sg[maxn+5][maxn+5][maxn+5];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
void DP(int L,int R){
    if (vis[L][R]) return;vis[L][R]=true;
    if (L==R){
        g[L][R][1]=f[L][R][1]=1;
        for (int x=1;x<=n;x++) sg[L][R][x]=sf[L][R][x]=1;
        return;
    }
    for (int i=L;i<R;i++) DP(L,i),DP(i+1,R);
    for (int x=2;x<=n && x<=a[L];x++) g[L][R][x]=f[L+1][R][x-1];
    for (int x=1;x<=n;x++){
        f[L][R][x]=g[L][R][x];
        for (int i=L;i<R;i++){
            f[L][R][x]=ADD(f[L][R][x],MUL(sf[L][i][x],g[i+1][R][x]));
            if (x<=a[i+1]) f[L][R][x]=ADD(f[L][R][x],MUL(f[L][i][x],sg[i+1][R][x-1]));
        }
    }
    for (int x=1;x<=n;x++)
        sg[L][R][x]=ADD(sg[L][R][x-1],g[L][R][x]),
        sf[L][R][x]=ADD(sf[L][R][x-1],f[L][R][x]);
}
int main(){
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    DP(1,n);for (int i=1;i<=n;i++) ans=ADD(ans,f[1][n][i]);
    printf("%d\n",ans);return 0;
}