题解：AT_abc252_g [ABC252G] Pre-Order

· · 题解

题目 link

注意到 n \le 500 可以区间 dp。设 f_{l, r} 表示序列 [l, r] 区间内合法森林的方案数，dp_{l, r} 表示 [l, r] 范围内一棵树的合法方案数，显然根是 l。显然有转移：

dp_{l, r} = f_{l + 1, r} \quad f_{l, r} = dp_{l, r} + \sum_{l < k \le r} dp_{l, k - 1} \times f_{k, r} \times [p_l < p_k]

做完了，答案就是 dp_{1, n}。

code