洛谷 [P3620] 数据备份

贪心神题

首先我们发现一个显然的贪心策略,连接相邻两个写字楼总是更优.

所以本题就变成了数轴上一堆点,要选 k 个彼此不相邻的区间,使得区间长度最小

对于 10000 的数据来说,我们可以用 DP 解决,

f[i][j]表示考虑前i个点，已经形成j对点的最小距离，num[i]表示第i个点的坐标。

如果这个点不与其他点组成一对，那么f[i][j]=f[i-1][j]。

否则这个点只能和前面的点组成一对，f[i][j]=f[i-2][j-1]+num[i]-num[i-1]。

f[i][j]=min(f[i-1][j],f[i-2][j-1]+num[i]-num[i-1]);

时间复杂度O(nk) ,可以滚动数组优化过。

对于全部数据来说,我们有一种非常奇特的贪心

这里有一个非常精妙的转化。假设在原先的n个点上有abcde5个相邻点(a<b<c<d<e)，我们把它差分以后就是ab,bc,cd,de四个值。

假设bc是最小的那个，我们贪心把bc选出来，然后加入答案以后删除。之后我们同时把与bc相邻的ab,cd取出来。把这三个值全都删除后合成一个新的值，这个值=ab+cd-bc。那么如果我们再次通过贪心原则把这个ab+cd-bc选出来加入答案，那么其中的-bc会和一开始选择的bc抵消，相当于我们这两次选择了ab+cd，也就是与bc相邻的两段。每一次选择会把已选择的段的数量+1，所以选择k次以后的ans就是最优解, 这类似于网络流的退流操作

我们需要用链表维护每个元素的前驱后继, 并且需要维护一个可以删除任意一个元素(不只是根元素)的堆,

这里有两种操作, 如果维护的值比较小,可以维护一个 bool 数组来标记被删除的元素, 如果被维护的元素很大, 我们需要维护一个删除堆, 每次询问的时候,比较删除堆与

原堆的堆顶, 如果一样就 pop

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#define ll long long

using namespace std;

const int MAXN = 100005;

int init() {

	int rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		rv = (rv<<1) + (rv<<3) + c - '0';

		c = getchar();

	}

	return fh * rv;

}

int n, k, loc[MAXN], num[MAXN], pre[MAXN], nxt[MAXN];

struct node {

	int wei, id;

	bool operator < (const node & b) const{

		return b.wei < wei;

	}

};

priority_queue<node> hea;

bool del[MAXN];

ll ans;

int main() {

	n = init(); k = init();

	for(int i = 1; i <= n; i++) {

		loc[i] = init();

		if(i >= 2) {

			num[i - 1] = loc[i] - loc[i - 1];

			hea.push((node){num[i - 1], i - 1});

		}

	}

	for(int i = 1; i <= n; i++) {

		pre[i] = i - 1; nxt[i] = i + 1;

	}

	nxt[0] = 1; nxt[n] = 0;

	num[0] = num[n] = 0x3f3f3f3f;

	for(int i = 1; i <= k; i++) {

		while(del[hea.top().id]) hea.pop();

		ans += hea.top().wei;int x = hea.top().id; hea.pop();

		int l = pre[x], r = nxt[x];

		del[l] = del[r] = 1;

		hea.push((node){num[x] = num[l] + num[r] - num[x], x});

		pre[x] = pre[l]; nxt[x] = nxt[r];

		pre[nxt[r]] = x; nxt[pre[l]] = x;

	}

	cout << ans << endl;

	return 0;

}

巴特西

洛谷 [P3620] 数据备份

贪心神题

最新文章

热门文章