算法
(区间DP) $O(n^3)$
本题本质上和 金字塔 一样
唯一的区别就是 dfs序
的定义不同
由于 dfs序
是连续区间,所以可以将整颗树按嵌套关系做如下划分:
$a, b, c$ 分别对应相应子树的根节点,需要满足 $a \leqslant b \leqslant c$
记 dp[l][r]
表示区间 $[l, r)$ 中满足存在某子树的 dfs序列
是 $\{A_l, \cdots, A_{r-1}\}$ 的树的个数
将 $A_l$ 作为根节点,然后再对 $[l+1, r)$ 做划分
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using mint = modint998244353;
mint dp[505][505];
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
rep(i, n+1) dp[i][i] = 1;
for (int w = 1; w <= n; ++w) {
rep(l, n) {
int r = l+w;
if (r > n) break;
dp[l][r] = dp[l+1][r];
for (int k = l+2; k < r; ++k) {
if (a[l+1] < a[k]) {
dp[l][r] += dp[l+1][k]*dp[k-1][r];
}
}
}
}
cout << dp[0][n].val() << '\n';
return 0;
}