Visibility Sequence

题目链接：ARC104F

题目大意

有一个数组 H，表示你构造的数组 X 中每一个位置的值上界，下界都是 1。
通过 X 构造数组 P，表示左边最后一个大于它的数的下标，如果没有就是 -1。
问你能构造出多少种不同的 P。

思路

发现数组长度只有 \(100\)，但是值域能到 \(1e5\)。
但是完全没有必要，因为你只是大小关系，你完全可以把超过数组长度的设成数组长度，顶多就是它们两两之间都不一样嘛。

然后你发现这个 \(P\) 有点像一棵树，每次 \(i\) 指向 \(P_i\)，最后会形成以 \(-1\) 为根的一棵树。
那问的就是这棵树能有多少形态呗。

而且边之间你放到区间里面是不会有交叉的，因为如果有 \(x,y,z,w\) 使得 \(z\rightarrow x,w\rightarrow y\)，那 \(x>z,y>w,w\geqslant z\)。
那 \(y>w\geqslant z\) 即 \(y>z\)，那不应该 \(z\rightarrow y\) 嘛。
所以是不交叉的。

那每个子树都是一个区间，你其实可以试着区间 DP。
然后你安排值，为了给后面留位置你肯定是能放多小放多小。
\(f_{l,r,k}\) 表示一棵树 \(l,r\) 区间，里面最大值是 \(k\)。
\(g_{l,r,k}\) 则表示森林的答案。

\(f_{l,r,k}=g_{l+1,r,k-1}\) 放一个根连着儿子。
\(g_{l,r,k}=\sum\limits_{mid=l}^{r-1}\sum\limits_{v=1}^kf_{l,mid,v}g_{mid+1,r,k}+\sum\limits_{mid=l}^{r-1}[a_{mid+1}\geqslant k]\sum\limits_{v=1}^{k-1}f_{l,mid,k}g_{mid+1,r,v}\)
一种是直接放进去，一种是抬高了后面再放进去。

还有一种区间 DP 法。
前面我们从小到大考虑，我们考虑从大到小。
\(f_{l,r,k}\) 表示 \(l,r\) 区间来处理，除了自己本身的限制还有值域的全部上界 \(k\)。

然后考虑从右往左枚举子树，因为子树之间那个儿子的值是要递增的。
那枚举最右边的那个子树的那个儿子的编号 \(mid\)，那右边 \([mid+1,r]\) 的值域就是 \(k-1\)，左边的就是 \(k\)。
两边方案乘起来，所以分的情况加起来即可。

代码

sol1

#include<cstdio>
#include<iostream>
#define ll long long
#define mo 1000000007

using namespace std;

const int N = 105;
int n, a[N];
ll f[N][N][N], g[N][N][N], fs[N][N][N], gs[N][N][N];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]); a[i] = min(n, a[i]);
	}
	
	for (int len = 1; len <= n; len++)
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			if (l == r) {
				f[l][r][1] = g[l][r][1] = 1;
				for (int i = 1; i <= n; i++) fs[l][r][i] = gs[l][r][i] = 1;
				continue;
			}
			for (int i = 2; i <= a[l]; i++) f[l][r][i] = g[l + 1][r][i - 1];
			for (int i = 1; i <= n; i++) {
				g[l][r][i] = f[l][r][i];
				for (int mid = l; mid < r; mid++) {
					(g[l][r][i] += gs[l][mid][i] * f[mid + 1][r][i] % mo) %= mo;
					if (i <= a[mid + 1]) (g[l][r][i] += g[l][mid][i] * fs[mid + 1][r][i - 1] % mo) %= mo;
				}
			}
			for (int i = 1; i <= n; i++) fs[l][r][i] = (fs[l][r][i - 1] + f[l][r][i]) % mo, gs[l][r][i] = (gs[l][r][i - 1] + g[l][r][i]) % mo;
		}
	
	ll ans = 0;
	for (int i = 1; i <= n; i++) (ans += g[1][n][i]) %= mo;
	printf("%lld", ans);
	
	return 0;
}

sol2

#include<cstdio>
#include<iostream>
#define ll long long
#define mo 1000000007

using namespace std;

const int N = 105;
int n, a[N];
ll rem[N][N][N];

ll slove(int l, int r, int k) {
	if (l > r) return 1;
	if (!k) return 0;
	if (l == r ) return 1;
	if (rem[l][r][k] != -1) return rem[l][r][k];
	rem[l][r][k] = 0;
	for (int mid = l; mid <= r; mid++) {
		int val = min(k, a[mid]);
		(rem[l][r][k] += slove(l, mid - 1, val) * slove(mid + 1, r, val - 1) % mo) %= mo;
	}
	return rem[l][r][k];
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) rem[i][j][k] = -1;
	printf("%lld", slove(1, n, n));
	
	return 0;
}

原文地址：http://www.cnblogs.com/Sakura-TJH/p/ARC104F.html