ARC127E 题解

shiruoyu114514 · 2025-05-15 11:50:29 · 题解

首先两种方案本质不同等价于其最后保留的数不同，等价于其删除的数不同。于是可以将问题转化为对删除集合计数。

显然当执行到一个 2 操作的时候，删除前面的哪个下标的 1 操作都可以。于是我们可以钦定 2 删除离其最近的一个没有删除的 1。

我们将这个操作序列改造一下：让每一个 2 “吸收”掉其应该删除的那个 1。这样操作就可以改成：当遇见一个 1 时，将一个数加入保留集合。遇见 2 时，把比当前保留集合还大的一个数加入删除集合。这本质上是延后计算所加的数，使前面在考虑决策的时候不会被后面的操作所干扰，没有后效性。

当保留集合与删数集合确定的时候，怎么安排才能使得限制更松？显然保留集合应该从小往大排序：当交换一对 i<j,a_i>a_j 时，<i 的删除数与 >j 的删除数约束不会有变化，而中间的 \ge a_i 的限制会变成 \ge a_j，更松了。

同理，删数集合也应该从小到大排序：交换 i<j,b_i>b_j 时，i 前 j 后不变，而中间的 a 限制从 < b_j 变成了 <b_i，更松了。

考虑对删数集合进行 DP。令 dp_{i,j} 为第 i 个删数位置选择 j 的方案数。显然两个“从小到大排序” 加上所有删数位置的数比所有之前的保留数大这两个限制就能够等价于所有的删数位置，它比所有前面的数大。其推论就是对于一个删数位置 i，如果其在原序列的位置为 p_i，则比其值小的数至少有 p_i-1 个，并且其数 b_{p_i} > b_{p_{i-1}}。

于是可以列出转移方程：

边界条件为 dp_{1,i} = [i \ge p_1]。前缀和优化即可做到 O(n^2)。