题解：CF2143D1 Inversion Graph Coloring (Easy Version)

Engulf · 2025-09-21 21:50:23 · 题解

若出现 i < j < k, b_i > b_j > b_k，就连成了一个奇环，这是无法红蓝染色的。也就是 b 的最长下降子序列 \textrm{LDS} \le 2。而这样，b 一定可以由最多 2 条上升子序列组成。

考虑动态规划，设 f_{i, x, y} 表示考虑了 a 的前 i 个元素，选择的子序列的第一条上升子序列最后一个元素为 x，第二条上升子序列最后一个元素为 y(y < x) 的方案数，若 y = 0，表示还没出现第二条。

注意 x, y 对应的是 值，而不是下标（当然，用下标表示也可以，但这没有用到 a_i\in[1,n] 的性质，也不利于 Hard Version 的思考）。

考虑转移，现在考虑 a_i：

• 不放入 a_i，f_{i,x,y}\leftarrow f_{i, x, y} + f_{i-1,x,y}，
• 放入 a_i
  • 若 a_i \ge x，可以将 a_i 加入第一条上升子序列末尾，f_{i, a_i, y}\leftarrow f_{i,a_i, y} + f_{i - 1,x,y}，
  • 否则，即 y \le a_i < x，可以将 a_i 加入第二条上升子序列末尾，f_{i, x, a_i} \leftarrow f_{i, x, a_i} + f_{i - 1, x, y}。
  • 否则，即 a_i < y，不能加入 a_i。

边界条件：f_{0, 0, 0} = 1。

答案