菜王的 blog

考虑一个 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)$，代码略。