题解

思路分析

这是一道 DP + 单调队列优化 的区间覆盖问题。

问题建模

• $N$ 个救生牛，每个工作时段为 $(s_i, t_i]$
• 需要解雇恰好 $K$ 头牛
• 求剩余牛覆盖的时刻数最大值

核心思路

1. 预处理去重

首先去除被完全包含的区间：

• 按左端点排序
• 如果区间 $i$ 被区间 $j$ 包含，删除区间 $i$
• 更新 $K$（已删除的区间数）

2. DP 状态定义

定义 $f[i][j]$ 表示：

• 考虑前 $i$ 个区间
• 删除了 $j$ 个区间
• 最大覆盖时刻数

3. 转移优化

对于区间 $i$，有两种选择：

• 保留：$f[i][j] = f[i-1][j] +$ 区间 $i$ 的贡献
• 删除：$f[i][j] = f[i-1][j-1]$

计算贡献时需要考虑与前面区间的重叠。

4. 单调队列优化

使用单调队列优化 DP 转移，避免重复计算重叠部分。

算法步骤

1. 预处理：

   • 按左端点排序
   • 删除被包含的区间

2. DP 转移：

   • 枚举区间和删除数量
   • 使用单调队列优化

3. 计算答案：

   • 取 $\max_{i=n-K}^{n} f[i][i+K-n]$

4. 输出结果

复杂度分析

• 排序：$O(N \log N)$
• DP：$O(N \cdot K)$
• 总时间复杂度：$O(N \log N + NK)$
• 空间复杂度：$O(NK)$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 1e2;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int n, m, ans;
int f[N + 5][M + 5];
int que[M + 5];

struct Seg {
	int l, r;
	bool friend operator < (Seg a, Seg b) {
		if (a.l == b.l) {
			return a.r < b.r;
		}
		return a.l < b.l;
	}
}p[N + 5];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].l >> p[i].r;
	}
	sort(p + 1, p + 1 + n);
	int tmpr = -INF, cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (p[i].r > tmpr) {
			p[++cnt] = p[i];
			tmpr = p[i].r;
		}
	}
	m -= (n - cnt);
	n = cnt;
	if (m <= 0) {
		tmpr = -INF;
		for (int i = 1; i <= n; i++) {
			ans += p[i].r - max(p[i].l, tmpr);
			tmpr = p[i].r;
		}
		cout << ans;
		return 0;
	}
	memset(f, -0x3f, sizeof f);
	for (int i = 0; i <= m; i++) {
		f[i][i] = 0;
	}
	for (int d = -1; d >= -n; d--) {
		int x = d + 1, sum = -INF;
		int l = 1, r = 0;
		for (int j = 0; j <= min(m, n + d); j++) {
			int i = j - d;
			while (l <= r && p[que[l]].r <= p[i].l) {
				sum = max(sum, f[que[l]][x + que[l]]);
				l++;
			}
			if (p[i - 1].r <= p[i].l) {
				sum = max(sum, f[i - 1][x + i - 1]);
			} else {
				while (l <= r && f[que[r]][x + que[r]] - p[que[r]].r <= f[i - 1][x + i - 1] - p[i - 1].r) {
					r--;
				}
				que[++r] = i - 1;
			}
			f[i][j] = sum - p[i].l + p[i].r;
			if (l <= r) {
				f[i][j] = max(f[i][j], f[que[l]][x + que[l]] - p[que[l]].r + p[i].r);
			}
		}
	}
	for (int i = n - m; i <= n; i++) {
		ans = max(ans, f[i][i + m - n]);
	}
	cout << ans;
	return 0;
}

题解

把所有区间按左端点升序、若左端点相同则按右端点升序排序。显然，若某个区间的右端点不超过前面出现过的最大右端点，那么不论保留与否都不会给答案带来贡献，可以直接删除，并把需要解雇的名额 K 相应减掉（这些牛等价于“免费删除”）。处理完之后得到的区间集合满足右端点严格递增。

若删完被支配的区间之后 K ≤ 0，说明我们已经解雇足够多人，此时只需顺序扫描一遍求所有区间的并长即可。

下面假设仍需再解雇 K 头牛。设排序后的区间为 p[1…n]，其中 p[i-1].r < p[i].r。我们令 dp[i][j] 表示在前 i 个区间中恰好解雇了 j 头牛，且第 i 个区间被保留下来时，能够覆盖的最大时间。为了转移，我们需要选择上一个保留的区间 t < i：中间的 i-t-1 个区间都被解雇，覆盖增量为

p[i].r - max(p[i].l, p[t].r),

而若两区间重叠，则只有第一次出现覆盖的区间可以把左端作为贡献。由于右端点串严格递增，p[t].r 是一个随 t 单调递增的函数，上述转移可以看成线性函数的最大值，因此我们可以沿着 j-i 为常数的对角线遍历 dp，并用单调队列维护在滑动窗口中的候选 t。这样就能把原本的 O(nK^2) 转移降低到 O(nK)。

最终答案等价于在最后一个区间之前保留 n-K 个区间时的最大覆盖值——代码中对所有可能的末尾位置 i 取 dp[i][i+K-n] 的最大值即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 1e2;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int n, m, ans;
int f[N + 5][M + 5];
int que[M + 5];

struct Seg {
	int l, r;
	bool friend operator < (Seg a, Seg b) {
		if (a.l == b.l) {
			return a.r < b.r;
		}
		return a.l < b.l;
	}
}p[N + 5];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> p[i].l >> p[i].r;
	}
	sort(p + 1, p + 1 + n);
	int tmpr = -INF, cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (p[i].r > tmpr) {
			p[++cnt] = p[i];
			tmpr = p[i].r;
		}
	}
	m -= (n - cnt);
	n = cnt;
	if (m <= 0) {
		tmpr = -INF;
		for (int i = 1; i <= n; i++) {
			ans += p[i].r - max(p[i].l, tmpr);
			tmpr = p[i].r;
		}
		cout << ans;
		return 0;
	}
	memset(f, -0x3f, sizeof f);
	for (int i = 0; i <= m; i++) {
		f[i][i] = 0;
	}
	for (int d = -1; d >= -n; d--) {
		int x = d + 1, sum = -INF;
		int l = 1, r = 0;
		for (int j = 0; j <= min(m, n + d); j++) {
			int i = j - d;
			while (l <= r && p[que[l]].r <= p[i].l) {
				sum = max(sum, f[que[l]][x + que[l]]);
				l++;
			}
			if (p[i - 1].r <= p[i].l) {
				sum = max(sum, f[i - 1][x + i - 1]);
			} else {
				while (l <= r && f[que[r]][x + que[r]] - p[que[r]].r <= f[i - 1][x + i - 1] - p[i - 1].r) {
					r--;
				}
				que[++r] = i - 1;
			}
			f[i][j] = sum - p[i].l + p[i].r;
			if (l <= r) {
				f[i][j] = max(f[i][j], f[que[l]][x + que[l]] - p[que[l]].r + p[i].r);
			}
		}
	}
	for (int i = n - m; i <= n; i++) {
		ans = max(ans, f[i][i + m - n]);
	}
	cout << ans;
	return 0;
}