专栏文章

题解：P10784 【MX-J1-T4】『FLA - III』Wrestle

RRindong
P10784题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqd554e
此快照首次捕获于
2025/12/04 02:51
3 个月前
此快照最后确认于
2025/12/04 02:51
3 个月前
查看原文

题意

有 nn 条红色线段和 mm 条蓝色线段，并且所有同颜色的线段两两间没有交集。红色线段有权重，蓝色没有。选出若干蓝色线段满足：
  • 在每一条红色线段内至多有一条蓝色线段被选中
  • 与选出的蓝色线段有交集的红色线段权重和不超过 kk
求满足这样情况下，最多的红蓝线段交集整点数是多少。

思路

首先注意到线段值域较大，考虑将所有红蓝线段离散化后重新映射下标。
然后发现蓝色线段的数量 m≤5000m \le 5000 ，权重的限制 k≤5000k \le 5000 ，对于每条蓝色线段来说只有选或不选，这就和我们学过的01背包非常相似了！我们可以把权重视为限制，设 dp[i][j][k]dp[i][j][k] 表示以第 ii 条线段结尾，权重限制为 jj ，当 k=0k = 0 时代表不选第 ii 条，k=1k = 1 时选择第 ii 条的最大交集整点数。于是我们有转移方程：
dp[i][j][k]={max⁡(dp[i−1][j][0],dp[i−1][j][1]),k=0max⁡(dp[l][j][0],dp[l][j][1])+Pi,k=1dp[i][j][k] = \begin{cases} \max(dp[i - 1][j][0], dp[i - 1][j][1]), & k = 0 \\ \max(dp[l][j][0], dp[l][j][1]) + P_i, & k = 1 \end{cases}
其中 ll 表示 <i< i 且不与 ii 冲突（也就是和 ii 不存在公共的红色线段）的最后一条线段。由于题目给的线段有非常好的性质，那么我们可以将线段按任意端点从小到大排序，就可以使用二分查找了！这样这道题的主要思路就讲完了，具体细节来看代码吧。

代码

CPP
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
const int N = 200010, M = 5005;
struct Red {
	int l, r, w;
	bool operator< (const Red& other) const {
		return l < other.l;
	}
} red[N], blue[M];
ll dp[M][M][2] = { 0 };
int dis[(N + M) << 1], dcnt = 0;
int Kpres[N];
ll Lpres[N];
int get_ind(int val) {
	int l = 1, r = dcnt, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (dis[mid] >= val) r = mid;
		else l = mid + 1;
	}
	return r;
}
int n, m, k;
//找到跟第 i 条线段冲突的第一个下标
int get_rgL(int lef) {
	int l = 0, r = n + 1, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (red[mid].r >= lef) r = mid;
		else l = mid + 1;
	}
	return r;
}
//找到跟第 i 条线段冲突的最后一个下标
int get_rgR(int rig) {
	int l = 0, r = n + 1, mid;
	while (l < r) {
		mid = l + r + 1 >> 1;
		if (red[mid].l <= rig) l = mid;
		else r = mid - 1;
	}
	return l;
}
int unique() {
	int ret = 0, las = -1;
	for (int i = 1; i <= dcnt; i++) {
		if (dis[i] != las)
			dis[++ret] = dis[i];
		las = dis[i];
	}
	return ret;
}
//两条线段的交集整点数
inline int get_inter(int l1, int r1, int l2, int r2) {
	return max(0, min(r1, r2) - max(l1, l2) + 1);
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		int l, r, w;
		scanf("%d%d%d", &l, &r, &w);
		red[i] = { l, r, w };
		dis[++dcnt] = l, dis[++dcnt] = r;
	}
	for (int i = 1; i <= m; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		blue[i] = { l, r, 0 };
		dis[++dcnt] = l, dis[++dcnt] = r;
	}
	sort(dis + 1, dis + 1 + dcnt);
	dcnt = unique();
	for (int i = 1; i <= n; i++)
		red[i].l = get_ind(red[i].l), red[i].r = get_ind(red[i].r);
	sort(red + 1, red + 1 + n);
	Kpres[0] = Lpres[0] = 0;
	for (int i = 1; i <= n; i++) {
		// Kpres 是权重的前缀和，Lpres 是长度前缀和
		Kpres[i] = Kpres[i - 1] + red[i].w;
		Lpres[i] = Lpres[i - 1] + (dis[red[i].r] - dis[red[i].l] + 1);
	}
	for (int i = 1; i <= m; i++)
		blue[i].l = get_ind(blue[i].l), blue[i].r = get_ind(blue[i].r);
	sort(blue + 1, blue + 1 + m);
	//放置哨兵，防止二分进行错误的命中
	red[0] = blue[0] = { -2, -1, 0 }, red[n + 1] = blue[m + 1] = { 10000000, 10000000 + 1, 0 };
	ll ans = 0;
	for (int i = 1; i <= m; i++) {
		int l = get_rgL(blue[i].l), r = get_rgR(blue[i].r);
		if (l > r) memcpy(dp[i], dp[i - 1], sizeof dp[i]);
		else {
			// p 是价值，w 是重量
			ll p = 0, w = Kpres[r] - Kpres[l - 1];
			if (l + 1 <= r - 1) p += Lpres[r - 1] - Lpres[l];
			if (l != r) p += get_inter(dis[blue[i].l], dis[blue[i].r],
				dis[red[r].l], dis[red[r].r]);
			p += get_inter(dis[blue[i].l], dis[blue[i].r],
				dis[red[l].l], dis[red[l].r]);
			int L = 0, R = m + 1, mid;
			//右端点大于等于最左边一项的右端点 
			while (L < R) {
				mid = L + R >> 1;
				if (blue[mid].r >= red[l].l) R = mid;
				else L = mid + 1;
			}
			r = R - 1;
			for (int j = 0; j <= k; j++) {
				dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
				dp[i][j][1] = dp[i][j][0];
				if (j >= w)
					dp[i][j][1] = max(dp[i][j][1], max(dp[r][j - w][0], dp[r][j - w][1]) + p);
				ans = max(ans, max(dp[i][j][0], dp[i][j][1]));
			}
		}
	}
	printf("%lld", ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...