『学习笔记』插入类dp

iCostalymh的博客 / 2023-08-14 / 原文

概述

可以说是一个套路化问题，想出来了就非常好做。前提是你得想出来。

转移方程一般也都是特定的：设 \(dp_{i, j}\) 表示往一个序列里插入了 \(i\) 个数，这 \(i\) 个数被分成了 \(j\) 段的方案数。

初始化：\(\begin{cases} dp_{1, i = 1} = 1 \\ dp_{1, i \ne 1} = 0 \end{cases}\).

一般来说分三类转移：

在某个段（的末尾）插入一个数：\(dp_{i, j} \leftarrow dp_{i, j} + dp_{i - 1, j}\).
新开一个段：\(dp_{i, j} \leftarrow dp_{i - 1, j - 1} \times j\).
合并两个段：\(dp_{i, j} \leftarrow dp_{i - 1, j + 1} \times j\).

这里要注意，这类转移方式是不考虑这些数插在什么位置的，也就是说，我们可以默认任意相邻的两个段的距离一定合法。

例题 P5999

这个题的主人公不是 \(\text {kangaroo}\)，而是 \(\text{zero4338}\)~

乍一看这题是 \(\text{zero4338}\) 反复横跳，实则分析一下会发现，这个数列一定满足：

\[\forall a_i, i \in [1, n], (a_i < a_{i - 1} \land a_i < a_{i + 1}) \lor (a_i < a_{i - 1} \land a_i < a_{i + 1}) \]

那么就可以套用这个插入型dp了。（我太菜了，一开始想的是记搜，但是没有记，是寄了）

我们按照 \(\text{from}\ 1\ \text{to}\ n\) 的顺序将每个数插入序列。

因为任意的 \(\{a_{i - 1}, a_i, a_{i + 1}\}\) 都不满足单调性，所以第一种转移方式就不能要了。

显然，\(s\) 和 \(t\) 插入的位置是固定的（\(1\) 位置一定插入 \(s\)，\(n\) 位置一定插入 \(t\)）。然后就魔改一下第二个转移方程：

\[\begin{cases} dp_{i, j} \leftarrow dp_{i - 1, j - 1} & i = s \lor i = t \\ dp_{i, j} \leftarrow dp_{i - 1, j - 1} \times (j - flag) & \text{elsewhere} \end{cases} \]

其中 \(flag\) 是 \(s\) 或 \(t\) 出现的次数。

解释：\(j - 1\) 个段，算上两边一共有 \(j\) 个空。但是我们还要考虑边界是 \(s\) 或 \(t\) 的情况。只讨论 \(s\) 的，\(t\) 的同理。如果最左边的段有 \(s\)（显然 \(s\) 一定在最左边的段的最左端），那么第 \(1\) 个空显然不能再插数了。\(t\) 的同理。

第三个就好说了：

\[\begin{cases} dp_{i, j} \leftarrow dp_{i - 1, j} & i = s \lor i = t \\ dp_{i, j} \leftarrow dp_{i - 1, j + 1} \times j & \text{elsewhere} \end{cases} \]

解释：插入 \(s\) 或 \(t\) 并将相邻的段与之合并时，它两边一定只有一个段，所以段数不变，且对于 \(s\) 或 \(t\) 只有一种情况。插入别的数并将相邻的段与之合并时，它两边一定有两个段，段数减一；因为 \(j + 1\) 个段，算上两边的有 \(j + 2\) 个空，不算两边的有 \(j\) 个空。合并两个段显然不能用第 \(i\) 个和第 \(j + 2\) 个，所以有 \(j\) 种情况。所以可得如上转移方程。

然后这个题就结束了。