ABC313Ex 题解

EuphoricStar · 2023-09-21 17:55:56 · 题解

考虑若重排好了 a，如何判断可不可行。显然只用把 b 排序，把 \min(a_{i - 1}, a_i) 也排序（定义 a_0 = a_{n + 1} = +\infty），按顺序逐个判断是否大于即可。

这启示我们将 \min(a_{i - 1}, a_i) 排序考虑。考虑从大到小加入 a_i，那么加入一个 a_i，和它相邻的 \min(a_{i - 1}, a_i) 一定是 a_i。每个时刻已经加入的 a_i 形成了若干个连续段，考虑连续段 dp：

设 f_{i, j} 为考虑了 a 中前 i 大的数，当前形成了 j 个连续段。那么有 i - j 对相邻的数。

初值为 f_{2, 2} = 1，表示一开始加入了 a_0 和 a_{n + 1}。

有转移：

• 把 a_i 接入一个段的开头或末尾，需要满足 a_i < b_{i - j}，此时有：f_{i, j} \gets f_{i - 1, j} \times (2j - 2)；
• 把 a_i 塞进两个相邻段的空隙中，然后合并这两个段，需要满足 a_i < b_{i - j + 1}，此时有：f_{i, j - 1} \gets f_{i - 1, j} \times (j - 1)。

答案为 f_{n + 2, 1}。

时间复杂度 O(n^2)。

code