P3620 [APIO/CTSC 2007] 数据备份
问题可以转化为 $n - 1$ 个数，其中选择 $k$ 个，使得选择的数的权值和最小。一种错误的贪心策略是优先直接权值最小的数，直接放弃其相邻的。
hack:
显然，选择 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$ 定为 $inf$ 。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #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;
}
|