P3620 [APIO/CTSC 2007] 数据备份

问题可以转化为 $n - 1$ 个数，其中选择 $k$ 个，使得选择的数的权值和最小。一种错误的贪心策略是优先直接权值最小的数，直接放弃其相邻的。

hack:

2 1 2 9

显然，选择 2 + 2 是最优解，但是错误的贪心策略会选择到 1 + 9 。考虑如何带悔贪心。对于已经选择的数 $w_{i}$ ，如果想要选择 $w_{i - 1}$ 或者 $w_{i + 1}$ 就一定要放弃 $w_{i}$ 。如果放弃 $w_{i}$ 仅仅只是为了 $w_{i - 1}$ 和 $w_{i + 1}$ 中的一个，则一定不是最优解，证明如下： $w_{i}$ 是先被选出的，一定比 $w_{i - 1}$ 和 $w_{i + 1}$ 都小。如果仅仅选择了 $w_{i - 1}$ 和 $w_{i + 1}$ 中的一个，则局部答案没有选择 $w_{i}$ 优；并且如果选择了 $w_{i + k}$ （其中 $k = 1$ 或 $k = - 1$ ），且不选择 $w_{i - k}$ ，那么不选或者不能再选的有 $w_{i - k}$ 、 $w_{i}$ 、 $w_{i + k}$ 、 $w_{i + k + 1}$ ，而如果选择了 $w_{i}$ ，则不选或者不能再选的只有 $w_{i - k}$ 、 $w_{i}$ 、 $w_{i + k}$ ，在全局上没有选择 $w_{i}$ 更优。因此，如果真的要放弃一个数了，必须要将它的左右的数都选上。在选择了一个数 $w_{i}$ 后，我们在堆里新插入一个数 $w_{i + 1} + w_{i - 1} - w_{i}$ ，在选择的次数上，原来的 $1$ 次变成了两次，在权值上，原来的 $w_{i}$ 变成了 $w_{i + 1} + w_{i - 1}$ ，刚好满足了题意。再考虑如何维护是否可选，在 $w_{i}$ 被选择之后，可以很轻松地将左右定位不可选，但是如果反悔之后如何让 $w_{i + 1}$ 和 $w_{i - 1}$ 的前后也不可选，这可以用双向链表维护。

另外注意的是，第 $1$ 个和第 $n - 1$ 个是不能再反悔的，将 $w_{0}$ 和 $w_{n}$ 定为 $i n f$ 。

查看代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
#define INF INT_MAX / 2
using namespace std;
const int N = 5e5 + 10;
int n, k, ans;
bool vis[N];
struct pos
{
    int wt, l, r;
}p[N];
priority_queue <pair <int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
void del(int x)
{
    p[x].l = p[p[x].l].l;
    p[x].r = p[p[x].r].r;
    p[p[x].l].r = x;
    p[p[x].r].l = x;
}
int main()
{
    int a;
    cin >> n >> k >> a;
    for (int i = 1, b; i < n; i++)
    {
        cin >> b;
        p[i].wt = b - a;
        a = b;
        p[i].l = i - 1;
        p[i].r = i + 1;
        q.push(make_pair(p[i].wt, i));
    }
    p[0].wt = p[n].wt = INF;
    for (int i = 1; i <= k; i++)
    {
        while (vis[q.top().second])
            q.pop();
        pair <int, int> x = q.top();
        q.pop();
        ans += x.first;
        vis[p[x.second].l] = vis[p[x.second].r] = true;
        p[x.second].wt = p[p[x.second].l].wt + p[p[x.second].r].wt - p[x.second].wt;
        q.push(make_pair(p[x.second].wt, x.second));
        del(x.second);
    }
    cout << ans;
    return 0;
}