洛谷P8591题解

题目链接：https://www.luogu.com.cn/problem/P8591。

分析

题意：给定 $n$ 条线段，需将每条线段染成红色或黑色。要求红色线段互不相交，且每条黑色线段至少与一条红色线段相交。目标是最小化红色线段的总长度和。

这道题的核心是选择合适的红色线段，既要保证它们互不相交，又要能 “覆盖” 所有黑色线段。也就是，所有未被选作红色的线段必须与至少一条红色线段相交，而红色线段之间不能有交集。

先将所有线段按左端点从小到大排序，便于后续的处理。

设 $f_i$ 表示前 $i$ 条线段中，第 $i$ 条线段为红色时的最小总长度和。

对于第 $i$ 条线段，寻找之前的红色线段 $j$ 并且 $j < i$，要求 $i$ 和 $j$ 不相交（满足 $l_i$ > $r_j$），且 $j$ 能覆盖中间可能存在的黑色线段。可以维护一个最大值 Max 来确保中间线段能被有效覆盖，这样更新 $f_i$ 的最小值。

最后在所有可能作为最后一条红色线段的 $f_i$ 中取最小值，该红色线段需能覆盖最后一条线段（如果最后一条是黑色）。

代码

#include <bits/stdc++.h>
using namespace std;
struct node {
	int l, r;
} a[3005];
bool cmp(node a, node b) {
	return a.l < b.l;
}
int f[3005];
int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
	sort(a + 1, a + n + 1, cmp);
	memset(f, 0x3f3f3f3f, sizeof(f));//将数组的每一项设为一个较大的数
	f[0] = 0;
	a[0].r = -1e9;
	for(int i = 1; i <= n; i++) {
		int Max = -1e9;
		for(int j = i - 1; j >= 0; j--) {
			if(a[i].l <= a[j].r || a[j].r < Max) continue;
			Max = max(Max, a[j].l);
			f[i] = min(f[i], f[j] + a[i].r - a[i].l);
		}
	}
	int ans = 1e9;
	for(int i = 1; i <= n; i++){
		if(a[i].r >= a[n].l) ans = min(ans, f[i]);
	}
	cout << ans;
	return 0;
}