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

ggc123 · 2025-08-07 22:19:15 · 题解

题目大意

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

思路

对于这样的一类问题，可以使用动态规划解决。

• 按照任务终止时间进行排序。

  对于此类任务调度问题，核心在于贪心策略和区间最优解。

  因为问题中可能会出现一个开始时间很早但终止时间很晚且价值很小的任务，优先选择这类任务肯定不是最优的。这也是按照任务终止时间进行排序而不是任务开始时间排序的原因。

• 不难发现，每一个任务都有选和不选两种选择。因此，我们使用 dp_i 表示对于前 i 个任务的最大价值。可以得出：

  dp_i=\max \left ( dp_{i-1},dp_x+val_i \right )

  其中，x 表示在当前任务发生前最晚结束的任务。

• 输出 dp_n。

代码

#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;
}