自动搬运

查看原文

来自洛谷，原作者为

	Svemit 藏锋、隐智、戒欲、省身、求实、慎言、节情、向善

搬运于2025-08-24 21:26:18，当前版本为作者最后更新于2023-06-03 10:29:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

更好的阅读体验

丢一发好理解又好写的线段树优化 dp。

题目传送门

简要题意

给定一个长为 $l$ 的线段，求出尽量少的不相交区间覆盖整段线段，要求题目给的所有子区间只被 $1$ 个区间覆盖。

分析

显然题目给的子区间 $[s, e]$ 中只有 $s$ 和 $e$ 端点能作为线段端点，所以我们应该给 $[s + 1, e - 1]$ 打上标记，这些不能作为线段端点。

令 $dp_i$ 为覆盖 $[0, i]$ 的最小的线段数量。

要求的就是 $\min (dp_j) + 1, j \in [i - a \times 2, i - b \times 2]$。

可以很轻易的写出一段暴力程序。

dp[0] = 0;
for(int i = 2; i <= l; i += 2) {
	if(flag[i]) continue;
	for(int k = a; k <= b; k ++) {
		int j = i - k * 2; // 在i, j 中间放一个线段
		if(j < 0) break;
		dp[i] = min(dp[i], dp[j] + 1);
	}
}

发现该算法的瓶颈会在枚举 $k$ 的复杂度太高了，考虑优化掉。

区间最小值？线段树？

每次取出区间中的最小值算出 $dp_i$ 递推下去就行。

代码就变成了这样：

	for(int i = a * 2; i <= l; i += 2) {
		if(flag[i]) continue;
		int ql = max(0, i - 2 * b), qr = i - 2 * a;
		dp[i] = query(ql, qr, 1) + 1;
		update(i, dp[i], 1);
	}

写一棵可爱的线段树就可以拉。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, l, a, b;
bool flag[N];
int c[N];
int dp[N];
struct segtree {
	int l, r, val;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define val(x) tr[x].val
} tr[N << 2];
void pushup(int x) {
	val(x) = min(val(x << 1), val(x << 1 | 1));
}
void build(int l, int r, int x) {
	l(x) = l, r(x) = r, val(x) = INF;
	if(l == r) return;
	int mid = l + r >> 1;
	build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
}
void update(int pos, int v, int x) {
	if(l(x) == r(x)) {
		val(x) = v;
		return;
	}
	int mid = l(x) + r(x) >> 1;
	if(mid >= pos) update(pos, v, x << 1);
	else update(pos, v, x << 1 | 1);
	pushup(x);
}
int query(int l, int r, int x) {
	if(l <= l(x) && r(x) <= r) return val(x);
	int mid = l(x) + r(x) >> 1, res = INF;
	if(l <= mid) res = query(l, r, x << 1);
	if(r > mid) res = min(res ,query(l, r, x << 1 | 1));
	return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n >> l >> a >> b;
	for(int i = 1; i <= n; i ++) {
		int x, y;
		cin >> x >> y;
		c[x + 1] ++, c[y] --;
	}
	for(int i = 1; i <= l; i ++) {
		c[i] += c[i - 1];
		if(c[i] > 0) flag[i] = true;
	}
	build(0, l, 1);
	update(0, 0, 1);
	for(int i = a * 2; i <= l; i += 2) {
		if(flag[i]) continue;
		int ql = max(0, i - 2 * b), qr = i - 2 * a;
		dp[i] = query(ql, qr, 1) + 1;
		update(i, dp[i], 1);
	}
	if(dp[l] >= INF) dp[l] = -1;
	cout << dp[l] << '\n';
    return 0;
}

upd: 将写错的 $[s + 1, e + 1]$ 改为 $[s + 1, e - 1]$，感谢 Aslf_Ek 指出错误。

upd: 在 Alisya 大佬的建议下将 $flag$ 数组的处理改为差分处理，复杂度更稳定。