ARC104F Visibility Sequence

大概有两种做法。

首先写一下官方题解的做法。

我们设 $i \to P_i$ 存在一条边，同时将 $P_i=-1$ 看做 $P_i = 0$ ，并添加虚点 $0$ ，于是对于任意一个排列，必然可以对应成为一棵树的形态。也就是说现在我们只需要统计这种树的种类数即可。

然后会发现，对于整棵树的一个子树，它必然在序列上对应一个区间，而它的根就是区间的左端点。考虑任意一个位置 $i$ ，它后面的第一个比它大的位置在 $j$ ，考虑 $[i+1,j-1]$ 这一段之间的所有数，显然它们不会连到 $i$ 的前面。再考虑 $j$ 向后的位置，它们不可能连到 $j$ 前面，因此 $i$ 的子树一定是这么一段区间。

考虑一棵子树，在删除根后它的儿子的子树就会构成一个森林。设子树从左到右的权值分别是 $A_1,A_2,\dots ,A_k$ ，当前位置的权值是 $A$ ，那么必然有

A > \max\{A_1,A_2,\dots ,A_k\}\\ A_1 \le A_2 \le \cdots \le A_k

因为如果这个位置 $\le$ 后面某个位置的权值，那么那个位置会成为这个位置的兄弟。而这些子树的权值如果不满足大小关系，内部就不是兄弟关系而是父子关系了。

显然，我们考虑所有点的权值都尽量小的时候一种树的形态是否存在，而且这样的话同一种树的形态必然对应唯一一种权值序列。

于是可以考虑设 $f[x][l][r]$ 表示区间 $[l,r]$ 构成了一棵树，根为 $l$ ，最小情况下权值是 $x$ ，设 $g[x][l][r]$ 表示区间 $[l,r]$ 构成了一个森林，森林最右边的树的根最小情况下的值为 $x$ 的方案数量。显然这种情况下权值不需要超过 $n$ ，于是可以直接给每个点的上限与 $n$ 取较小值。

考虑转移。

所以树的转移很简单

f[x][l][r] = g[x-1][l + 1][r]

考虑森林的转移，这种转移的常见操作是枚举一棵树，然后分成一棵树和剩下的森林，这里显然枚举后面的树会比较方便。由于 $g[x][l][r]$ 表示的是权值最小的情况下最右边的子树权值是 $x$ 的森林个数，所以转移的时候，需要满足两边必须有一边的最小情况下的的权值是 $x$ 。如果是左边满足，那么直接把右边的子树的根的权值变成 $x$ ，如果右边满足就没必要修改。

g[x][l][r] = f[x][l][r] + \sum_{\max(a,b) = x} \sum_{p=l}^{r-1} f[a][l][r]\times g[b][l][r]

这样就可以不重不漏计算了，复杂度是 $O(n^4)$ 。一份代码。

还有一种 zjk 做法（非常好写）。

类似刚刚的思路，考虑所有点的权值都尽量小的情况下，会发现一棵原题中的树会对应唯一一种笛卡尔树。因为会发现原题中的树进行一次左兄弟，右儿子的变化后就会成为一棵笛卡尔树！不难发现做完这个操作后，这个笛卡尔树必须满足左儿子和当前点可以相等，而右儿子必须小于。

一张看起来非常阳间的配图：

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 126
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 1e9 + 7;
int n , m;
int A[MAXN];

vi val;
int dp[MAXN][MAXN][MAXN];

int fuck( int l , int r , int x ) {
	int& s = dp[l][r][x];
	if( ~s ) return s;
	if( l > r ) return s = 1;
	if( !x ) return 0;
	s = 0;
	rep( p , l , r ) s = ( s + fuck( l , p - 1 , min( x , A[p] ) ) * 1ll * fuck( p + 1 , r , min( x , A[p] ) - 1 ) ) % P;
	return s;
}

void solve() {
	cin >> n;
	rep( i , 1 , n ) scanf("%d",A + i) , A[i] = min( A[i] , n );
	memset( dp , -1 , sizeof dp );
	cout << fuck( 1 , n , n ) << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}