Solution「『CF2161D Locked Out』题解」

denominator · 2025-11-24 08:56:52 · 题解

退役之前整理自己的遗物，把最后一篇想写的 tj 写完。

其实也是第一次写 hint 驱动式的 tj。

:::info[题意]{open} 原题

• 一个序列 b 是好的，当且仅当不存在 1\leq i<j\leq n，使 b_j-b_i=1。
• 给定一个序列 a，求需要删除多少个数才能使得它变成好的。
• 多组数据，1\leq n\leq3\times10^5，1\leq a_i\leq n。 :::

::::info[提示 1] 考虑如何刻画「好的」序列。

:::info[提示 1.1] 如果 l\sim r 的每一个数都存在于序列 b 中，那它们应该排列成什么形状？ :::

:::info[提示 1.2] 如果 x 不存在于序列 b 中，那小于 x 的数和大于 x 的数之间有影响吗？ :::

:::success[答案] 如果 l\sim r 的每一个数都存在于序列 b 中，那它们必须排成 r,r,\cdots,r,r-1,r-1,\cdots,r-1,\cdots,l,l,\cdots,l 的形状，即单调不增。

这样子可以形成多个在值域上连续的段。「好的」序列即将这些段之间交错拼接。 ::: ::::

::::info[提示 2] 考虑如何贪心地维护这样的序列。

:::info[提示 2.1] 考虑从小到大枚举序列里的一个数值 x，讨论它要加进已经是「好的」且值均 <x 的子序列中的情形。 :::

:::info[提示 2.2] 添加方案只有以下两种：

• 将 x 添加到 x-1 的头部（不添加 x 也属于这一种情形）；
• 撤回添加 x-1 的操作，以保证 x 完全添加到序列中。 ::: ::::

:::success[题解] 阅读提示。

枚举序列 a，把每个数的出现位置罗列出来。

在提示 2.1 的情形下，考虑提示 2.2 的两种情况。

• 第一种情况：考虑类似归并排序地合并值为 x 的子序列与已经加入的、值为 x-1 的子序列，并且在合并的过程中计算答案。
• 第二种情况：直接继承 x-2 时计算的答案。

从中选择更优的即可。

我们讨论了两种情况，却说明从中选出更优的。但是，如果两个方案同样优秀怎么办？

这个和一般的 dp 不一样：这一步的选择直接影响到了加入的值为 x 的元素，进而影响 x+1 时答案的计算。

这时我的选择是：应当选用第二种情况。原因很简单：若对于 x+1，第一种情况的答案为 t，那么对于第二种情况，删除值为 x 的元素时可以选择与第一种情况时删的一样，这样答案也可以到达 t。

不过实测结果是，选用第一种情况也可以。不知道为什么。 :::

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int T, n, a[N], dp[N], rt[N];
vector <int> pos[N];
int main () {
    scanf ("%d", &T);
    while (T --> 0) {
        scanf ("%d", &n);
        fill (pos + 1, pos + n + 1, vector <int> ());
        for (int i = 1; i <= n; i++) {
            scanf ("%d", &a[i]);
            pos[a[i]].push_back (i);
        }
        rt[1] = pos[1].size () - 1;
        for (int i = 2; i <= n; i++) {
            int t = -1, s = pos[i].size ();
            for (int j = 0, k = 0; j <= rt[i - 1] || k < (int) pos[i].size (); ) {
                if (k == (int) pos[i].size () || (j <= rt[i - 1] && pos[i - 1][j] < pos[i][k])) {
                    j++;
                } else {
                    int u = j + pos[i].size () - k - 1;
                    if (u < s) {
                        t = k;
                        s = u;
                    }
                    k++;
                }
            }
            if (dp[i - 2] + (int) pos[i - 1].size () >= dp[i - 1] + s) {
                dp[i] = dp[i - 1] + s;
                rt[i] = t;
            } else {
                dp[i] = dp[i - 2] + pos[i - 1].size ();
                rt[i] = pos[i].size () - 1;
            }
        }
        printf ("%d\n", dp[n]);
    }
    return 0;
}