文章目录

dp trick 之「连续段插入 dp」

模拟赛 T2 遇到的。

对这类问题，一般会按值大小插入以消除后效性，先只在每段内考虑限制，再在两个段合并时考虑限制。

题意转化为求有多少个 $1 \sim n$ 的排列 $p$ 满足 $p_i$ 两边的数字同时大于或同时小于 $p_i$，且 $p_1 = s, p_n = t$。

设 $f_{i, j}$ 表示前 $i$ 个数，分成 $j$ 段的方案数。从小到大加入每个数，对于 $i \neq s$ 且 $i \neq t$：

新开一段：那么最终插入在 $i$ 两边的数一定是后来插入的，所以一定比 $i$ 大，满足限制。一共有 $j$ 个空可以放，如果其 $> s$ 那不能放在开头，如果其 $> t$ 则不能放在结尾。
$$ f_{i, j} = f_{i - 1, j - 1} \times (j - [i > s] - [i > t]) $$
接在某段的头 / 尾：一定有一侧的数是小于 $i$ 的，有一侧是大于 $i$ 的，不满足限制。
将两端连起来：此时 $i$ 两侧的数都 $< i$，符合限制。上一步操作完有 $j + 1$ 段，所以一共有 $j$ 个空能放。
$$ f_{i, j} = f_{i - 1, j + 1} \times j $$

转移即为把情况一、三加起来。

如果 $i = s$ 或 $i = t$，那么就将其插在开头或结尾。此时可以新开一个段，也可以并到开头或结尾的段去。

$$ f_{i, j} = f_{i, j} + f_{i, j + 1} $$

最后答案是 $f_{n, 1}$。

先转化一下。如果说把所有磁铁最紧密的排列在一起，设他们之间的长度为 $k$，那么还剩下 $l - k$ 个空位，要将其插到这些磁铁中间，插板法可知方案数为 $\binom{l - k + n}{n}$。那我们只需要求长度为 $k$ 的排列紧密的磁铁方案数。

于是在原先的 dp 上再加一维。$f_{i, j, k}$ 表示前 $i$ 个数，分成 $j$ 段，长度为 $k$ 的方案数，答案即为 $\sum f_{n, 1, i} \times \binom{l - i + n}{n}$。

转移的考虑方法和上题类似。