考虑连边 \((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;
}
- Visibility Sequence AtCoder Regular Contestvisibility sequence atcoder regular atcoder regular contest 165 multiples sequence atcoder regular minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest sliding atcoder regular contest 167 atcoder regular contest degree atcoder regular contest builder atcoder regular contest 164