自动搬运

查看原文

来自洛谷，原作者为

	vegetable_king 全身全霊！MORE MORE JUMP!!

搬运于2025-08-24 22:48:53，当前版本为作者最后更新于2023-08-04 14:26:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑一个 dp，设 $f_{k, i, j}$ 表示目前填了 $0 \sim k$，这些数最左的在 $i$，最右的在 $j$。发现每次新填入 $k + 1$，填的位置不可能在 $[i, j]$ 内，因为这样就不存在 $\operatorname{mex} = k + 1$ 的区间了。所以，$k + 1$ 只能填在 $i - 1, j + 1$ 其中之一位置，否则就留出了不能填的空隙，导致后填的数位置不足。

于是填下的位置一定是连续的一段，即 $k = j - i$，我们就可以省略 $k$，转移显然：

$$f_{i, i} = [i > L_0 \vee n - i \ge L_0]$$ $$f_{i, j} = [j > L_k]f_{i, j - 1} + [n - i \ge L_k]f_{i + 1, j} (i < j) $$

时间复杂度为 $O(n^2)$，代码略。