[DP记录]ARC104F Visibility Sequence

**题意** ： 对于的序列 $H_{1\sim n}$ ，定义其“前邻序列”为 $P_{1\sim n}$ ，其中 $P_i=\max\{{j:j<i,H_j>H_i}\}$ ，特殊地，若不存在 $j$ 满足条件，则 $P_i=-1$。 现在给定序列 $X_{1\sim n}$ ，请问对于所有满足 $1≤H_i≤X_i$ 的序列 $H_{1 \sim n}$ ，有多少个不同的“前邻序列”。 答案对 $10^9+7$ 取模。 $n\le 100,x\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 经典的给个映射求投影大小。具体流程有： - 先观察 $H\rightarrow P$ ，找出 $P$ 的某些必要性质 - 证明这性质是充分的（不对 $H$ 设限，看是否对于每个满足性质的 $P$ 都存在 $H_*\rightarrow P$） - 找出满足 $H\rightarrow P$ 的 $H$ 的充要条件 （注意，上一步相当于构造特例，这一步是描述解集） - 考虑 $X$ 的限制，构造判定 “是否存在 $H$ 使得 $H\rightarrow P$ ” 的算法。 - 根据上述判定算法设计 DP ，进行计数。 ------------ $P$ 是一种下标关系，可以写成图的形式，便于观察。对于每个 $i$ 连边 $i\rightarrow P_i$ 。若 $P_i=-1$ 则不连边。 除了 $P_i=-1$ 的情况，每个点都恰有一条向前连的出边，图为**内向树森林**。 可以发现， $1\sim n$ 显然是这森林的 dfs 序之一。 观察片刻，这条性质应当很充分了。考虑不对 $H$ 加以限制，是否能构造出所有满足上述性质的树。 答案是肯定的。对于一片满足性质的森林，把标号从前往后从小往大划分，转化为满足性质的树，则这些树之间不相干了。对于每棵树，给根填上目前值域的最大值，然后又转化为森林。 不难进一步总结出 $H\rightarrow P$ 的 $H$ 的充要条件： 对于节点 $u$ ，必须有 $H_u>\max\limits_{v\text{是}u\text{儿子}}H_v$ ，且 $H_u\geq $ 上一个兄弟 $H_{u'}$。 ------------ 接下来考虑如何判定某个 $P$ 能否被生成。简单起见，我们希望为 $P$ 构造一个对应的“最优”的 $H_0$ ，使得若 $H_0$ 不满足条件，其余方案也不满足。（这样在判定时，和 $X$ 的具体取值关系很简单，这是一个好兆头） 观察 $X$ 对 $H$ 的限制，每个位置都有一个上界。我们要让 $H_0$ 的每一位同时达到下界。这并不一定总能实现，但我们不妨试试，毕竟那些不能实现的情况往往太过复杂，不值得优先考虑。 观察前文的充要条件，一个 $H$ 的约束基于其余若干 $H$ 的 $\max$ 。那当然是他们都取得下界的时候，该 $H$ 也能取得下界，于是不难归纳证明各个位置的下界能同时取得，好耶！ 具体方案也非常简单，只需要根据充要条件，按 dfs 序考虑，每次取能取的最小值即可。 ------------ 接下来考虑如何计数。 由于 $1\sim n$ 是这森林的 dfs 序，每个子树的 dfs 序必然是一个编号区间。 设 $f_{l,r,x}$ 为 $[l,r]$ 形成一棵树的情况，且 $H_l=x$ （子树的根）。 $g_{l,r,x}$ 为 $[l,r]$ 形成一片森林的情况，其中最大权值（最后一棵树的根）为 $x$ 。 这里显然有 $x\leq r-l+1$ 。 边界：$f_{i,i,1}=g_{i,i,1}=1$ 。 对于 $f$ ，只需在 $g$ 的基础上加一个根，则 $f_{l-1,r,x+1}=[X_{l-1}\geq x+1]g_{l,r,x}$ 。 对于 $g$ ，枚举**最后一棵树** $[k+1,r]$ ，这样最大值的位置就确定为 $k+1$，有转移 ： $$g_{l,r,x}=f_{l,r,x}+\sum\limits_{k=l,\ X_{k+1}\geq x}^{r-1}\Bigg(f_{l,r,x}\sum\limits_{c=l}^xg_{k+1,r,c}\Bigg)+\Bigg(g_{k+1,r,x}\sum\limits_{c=l}^{x-1}f_{l,k,c}\Bigg)$$ （其实是当 $f_{l,k,x_1},g_{k+1,r,x_2}$ 的 $\max(x_1,x_2)=x\leq X_{k+1}$ 时能转移） 对 $c$ 前缀和优化，记 $Sf_{l,r,x}=\sum\limits_{c=l}^xf_{l,k,c},Sg_{l,r,x}=\sum\limits_{c=l}^xg_{l,k,c}$ ，然后暴力求和。 复杂度 $O(n^4)$。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 105 using namespace std; const int mod=1000000007; int g[MaxN][MaxN][MaxN],f[MaxN][MaxN][MaxN] ,sg[MaxN][MaxN][MaxN],sf[MaxN][MaxN][MaxN]; int n,X[MaxN]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&X[i]); for (int i=1;i<=n;i++) f[i][i][1]=g[i][i][1]=sf[i][i][1]=sg[i][i][1]=1; for (int len=2;len<=n;len++) for (int l=1;l+len-1<=n;l++){ int r=l+len-1; for (int x=1;x<=r-l+1;x++){ if (X[l]>=x)f[l][r][x]=g[l+1][r][x-1]; g[l][r][x]=f[l][r][x]; for (int k=l;k<r;k++)if (X[k+1]>=x) g[l][r][x]=(g[l][r][x] +1ll*g[l][k][x]*sf[k+1][r][min(x,r-k)] +1ll*f[k+1][r][x]*sg[l][k][min(x-1,k-l+1)] )%mod; } for (int x=1;x<=r-l+1;x++){ sf[l][r][x]=(sf[l][r][x-1]+f[l][r][x])%mod; sg[l][r][x]=(sg[l][r][x-1]+g[l][r][x])%mod; } } int ans=0; for (int x=1;x<=n;x++)ans=(ans+g[1][n][x])%mod; printf("%d",ans); return 0; } ```