专栏文章

题解：SP130 RENT - Rent your airplane and make money

gggc123
SP130题解参与者 1已保存评论 0

文章操作

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

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

题目大意

给定 nn 个任务。对于每一个任务都有初始时间 lil_i、终止时间 rir_i 和价值 valival_i。选择一组任务使得任务的时间区间不重合，求这组任务价值的最大值。

思路

对于这样的一类问题，可以使用动态规划解决。
  • 按照任务终止时间进行排序。
    对于此类任务调度问题，核心在于贪心策略和区间最优解。
    因为问题中可能会出现一个开始时间很早但终止时间很晚且价值很小的任务，优先选择这类任务肯定不是最优的。这也是按照任务终止时间进行排序而不是任务开始时间排序的原因。
  • 不难发现，每一个任务都有选和不选两种选择。因此，我们使用 dpidp_i 表示对于前 ii 个任务的最大价值。可以得出：
    dpi=max⁡(dpi−1,dpx+vali)dp_i=\max \left ( dp_{i-1},dp_x+val_i \right )
    其中，xx 表示在当前任务发生前最晚结束的任务。
  • 输出 dpndp_n。

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5+5;
struct node {
	int l, r, val;
	bool operator<(const node other)const {
		return r < other.r;
	}
} a[N];
int T, n, dp[N];

signed main() {
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++)	cin >> a[i].l >> a[i].r >> a[i].val;
		for (int i = 1; i <= n; i++)	a[i].r += a[i].l;
		sort(a + 1, a + 1 + n);

		dp[0] = 0;	// 多组问题不要忘记初始化，警钟敲烂
		for (int i = 1; i <= n; i++) {
			int x = lower_bound(a + 1, a + i, (node) { 114, a[i].l, 514 }) - a - 1;
			dp[i] = max(dp[i - 1], dp[x] + a[i].val);
		}
		cout << dp[n] << "\n";
	}
	return 0;
}

评论

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

正在加载评论...