考虑连边 \((i,p_i)\)（若 \(p_i = -1\) 则不连边），可以发现形成了一篇内向树森林且这个森林存在一个 dfs 序为 \(1,2,...,n\)。
这棵森林有如下性质：
- \(\forall v \in son_u,h_u > h_v\)
- \(\forall v,w \in son_u \land v < w,h_v \le h_w\)
考虑一个 \(p\)，我们寻找一个最优的 \(h_0\)，使得它能生成 \(p\)。显然 \(h_0\) 的每个数都要取到下界。
因为一棵树的点编号为连续的区间，所以考虑区间 dp。
设 \(f_{i,j,x}\) 为 \([i,j]\) 形成了一棵树且 \(h_i = x\) 的方案数，同时设 \(g_{i,j,x}\) 为 \([i,j]\) 形成了一片森林且最后一棵树的根的 \(h\) 值 \(= x\) 的方案数。
有转移：
- \(f_{i,j,x} \gets g_{i+1,j,x-1}\)，表示以 \(i\) 为根将 \([i+1,j]\) 的森林连起来。
- \(g_{i,j,x} \gets f_{i,j,x}\)，表示一棵树也算森林。
- \(g_{i,j,x} \gets \sum\limits_{k=i}^{j-1} [x \le a_{k+1}] \sum\limits_{t=1}^x g_{i,k,t} \times f_{k+1,j,x}\)，表示枚举这片森林的最后一棵树（此时森林一定要有至少两棵树）的树根 \(k+1\)，\(h_{k+1}=x\)，前面的数的 \(h\) 值都要 \(\le x\)。
- \(g_{i,j,x} \gets \sum\limits_{k=i}^{j-1} [x \le a_{k+1}]g_{i,k,x} \times \sum\limits_{t=1}^{x-1} f_{k+1,j,t}\)，仍然表示枚举最后一棵树的根 \(k+1\)，但是 \(h_{k+1} < x\)，此时把最后一棵树的 \(h\) 值整体加直至 \(h_{k+1} = x\)。\(< x\) 是因为要避免算重。
答案即为 \(\sum\limits_{x=1}^n f_{1,n,x}\)。
直接转移是 \(O(n^5)\) 的，因此再设 \(sf_{i,j,x} = \sum\limits_{t=1}^x f_{i,j,x},sg_{i,j,x} = \sum\limits_{t=1}^x g_{i,j,x}\)，这样整道题就变成 \(O(n^4)\) 了。
code
// Problem: F - Visibility Sequence
// Contest: AtCoder - AtCoder Regular Contest 104
// URL: https://atcoder.jp/contests/arc104/tasks/arc104_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
const ll mod = 1000000007;
int n, a[maxn];
ll f[maxn][maxn][maxn], g[maxn][maxn][maxn], sf[maxn][maxn][maxn], sg[maxn][maxn][maxn];
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
a[i] = min(a[i], n);
f[i][i][1] = g[i][i][1] = 1;
for (int j = 1; j <= n; ++j) {
sf[i][i][j] = sg[i][i][j] = 1;
}
}
for (int p = 2; p <= n; ++p) {
for (int i = 1, j = p; j <= n; ++i, ++j) {
for (int x = 1; x <= a[i]; ++x) {
g[i][j][x] = f[i][j][x] = g[i + 1][j][x - 1];
}
for (int k = i; k < j; ++k) {
for (int x = 1; x <= a[k + 1]; ++x) {
g[i][j][x] = (g[i][j][x] + sg[i][k][x] * f[k + 1][j][x] % mod + g[i][k][x] * sf[k + 1][j][x - 1] % mod) % mod;
}
}
for (int x = 1; x <= n; ++x) {
sf[i][j][x] = (sf[i][j][x - 1] + f[i][j][x]) % mod;
sg[i][j][x] = (sg[i][j][x - 1] + g[i][j][x]) % mod;
}
}
}
printf("%lld\n", sg[1][n][n]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}