自动搬运

查看原文

来自洛谷，原作者为

	waaadreamer **

搬运于2025-08-24 22:04:58，当前版本为作者最后更新于2018-09-24 21:31:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

月赛的时候有事没考……后来才看到这题出的超棒！手动膜zcy……

刚开始以为是一个网络流模型，然后建模建了十几分钟没成功……后来猛然间想到离散化之后分类讨论线段端点似乎可行。

考虑到我们只需要求出关门的最长时间即可。于是可以给每个考察队建一个带权点，然后进行如下操作：

1.一个线段左边为起点，右边为终点。如果这两个点同属于一个考察队，那么就给该点权加上当前线段长度，表示如果给该考察队钥匙可以获得的贡献；否则就在分属的两个考察队之间连一条权值为线段长度的边，表示如果给这两个考察队钥匙可以获得的贡献。

2.一个线段左边和右边都是起点，则给左边的考察队点权加上线段长度，原因同上；

3.一个线段左边和右边都是终点，则给右边的考察队点权加上线段长度；

4.一个线段左边是终点，右边是起点，则必然给答案造成贡献，直接给答案加上贡献即可。

接下来我想着这个图懵了一会儿，怎么求解从中选k个点使得诱导子图的权值和最大？刚开始想着这个图是个二分图，可以怎么做；后来猛然发现这个图实际上是由很多链组成的……

于是就很显然了，对于每条链都dp一下，dp[i][j][0/1]就表示当前dp到了前i个点，选j个点，当前点是否选择的最大值，这个dp是很easy的，于是问题就在O(n^2)的时间内解决了。

再次膜出题人Orz……/菜鸡的我刚开始连dp的初始值都没赋2333

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2005;
map<int, int> mp;
int srt[maxn * 2], f[maxn][maxn][2], val[maxn], ss[maxn];
int vis[maxn], nxt[maxn], ord[maxn], tot, n, m;
void dfs(int u){
	vis[ord[++tot] = u] = 1;
	if(nxt[u]) dfs(nxt[u]);
}
int main(){
	freopen("input.txt", "r", stdin);
	freopen("out1.txt", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		int l, r;
		scanf("%d%d", &l, &r);
		mp[l] = i * 2;
		mp[r] = i * 2 + 1;
		srt[i] = l;
		srt[i + n] = r;
	}
	sort(srt + 1, srt + n + n + 1);
	int res = 0;
	for(int i = 1; i < n + n; i++){
		int l = srt[i], r = srt[i + 1];
		int ld = mp[l], rd = mp[r];
		if((ld & 1) && !(rd & 1)) res += r - l;
		if((ld & 1) && (rd & 1)) val[rd >> 1] += r - l;
		if(!(ld & 1) && !(rd & 1)) val[ld >> 1] += r - l;
		if(!(ld & 1) && (rd & 1)){
			if((ld >> 1) == (rd >> 1)) val[ld >> 1] += r - l;
			else nxt[rd >> 1] = ld >> 1, ss[rd >> 1] = r - l;
		}
	}
	for(int i = 1; i <= n + n; i++){
		int d = mp[srt[i]];
		if(!(d & 1) && !vis[d >> 1]) dfs(d >> 1);
	}
	//for(int i = 1; i <= n; i++) printf("%d ", ord[i]);
	memset(f, 0xbf, sizeof(f));
	f[n + 1][0][0] = 0;
	for(int i = n; i > 0; i--){
		f[i][0][0] = 0;
		for(int j = min(n - i + 1, m); j > 0; j--){
			f[i][j][0] = max(f[i + 1][j][0], f[i + 1][j][1]);
			if(!nxt[ord[i]]) f[i][j][1] = max(f[i + 1][j - 1][0], f[i + 1][j - 1][1]) + val[ord[i]];
			else f[i][j][1] = max(f[i + 1][j - 1][0], f[i + 1][j - 1][1] + ss[ord[i]]) + val[ord[i]];
		}
	}
	printf("%d\n", srt[n + n] - srt[1] - res - max(f[1][m][0], f[1][m][1]));
	return 0;
}
```