P9493 进行一个列的排 题解

· · 题解

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