题目描述

小 K 有 $N$ 项工作。第 $i$ 项工作需要花费 $t_i$ 单位时间，必须在 $d_i$ 时刻或之前完成，完成后可以获得 $p_i$ 的报酬。
小 K 从时刻 0 开始工作。在同一时刻，他只能做一项工作。一旦开始一项工作，就必须连续完成，不能中断或切换。
目标是选择一部分工作并安排它们的执行顺序，使得所有被选中的工作都能在各自的截止时间前完成，并且获得的总报酬最大。

样例

输入:
3
5
1 2 50
3 3 100
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 20
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 100
1 5 1
3 2 5000
5 5 800

输出:
101
80
800

算法 (动态规划 - 类似 0/1 背包)

$O(N \log N + N \times D_{max})$

思路分析

1. 问题性质: 这是一个带有时间约束的选择和调度问题。我们需要选择一个子集的工作，并确定它们的执行顺序，以最大化总收益，同时满足每个选定工作的截止时间要求。

2. 排序: 如果我们已经选定了一组工作，那么按照它们的截止日期 $d_i$ 升序 执行这些工作总是最优（或者说至少是一种最优策略）的。这被称为 Earliest Deadline First (EDF) 策略的思想。为什么呢？假设我们有一个可行的调度，但其中存在两个相邻执行的工作 $i$ 和 $j$，$i$ 在 $j$ 之前执行，但 $d_i > d_j$。设 $i$ 的完成时间为 $C_i$， $j$ 的完成时间为 $C_j = C_i + t_j$。由于调度可行，$C_i \le d_i$ 且 $C_j \le d_j$。现在交换它们的顺序，让 $j$ 先执行，完成时间为 $C’_j = (\text{start time}) + t_j$，然后 $i$ 执行，完成时间为 $C’_i = C’_j + t_i = (\text{start time}) + t_j + t_i = C_j$。在这个新顺序中，$j$ 的完成时间 $C’_j = C_j - t_i$。因为 $C_j \le d_j$，所以 $C’_j < d_j$ 仍然满足。$i$ 的完成时间 $C’_i = C_j$。我们知道 $C_j \le d_j < d_i$，所以 $C’_i < d_i$ 也满足。交换后调度仍然可行，且完成时间不变或提前。因此，按截止日期排序不会损失最优性。
   基于这个观察，我们可以先将所有 $N$ 项工作按照它们的截止时间 $d_i$ 从小到大排序。

3. 动态规划: 排序后，我们可以尝试用动态规划来解决。这个问题可以看作是一个选择问题，与 0/1 背包问题有相似之处。

   • 状态定义: 考虑时间维度。我们可以定义 dp[j] 为：在考虑了按截止日期排序后的前 $i$ 个工作后，所有选定工作的总完成时间恰好为 $j$ 时，可以获得的最大报酬。但这种定义似乎不太好处理截止日期。
   • 更合适的状态定义: 让我们定义 dp[j] 为：考虑了按截止日期排序后的前 $i$ 个工作后，找到一个可行的工作子集，使得这些工作的最后完成时间不超过 $j$，并且获得的总报酬最大。

4. 状态转移: 我们按照按 $d_i$ 排序后的顺序来处理每个工作 $i$（时间 $t_i$，截止 $d_i$，报酬 $p_i$）。当我们考虑工作 $i$ 时，我们需要更新 dp 数组。对于一个时间点 $j$，我们有两种选择：

   • 不选择工作 $i$: 那么 dp[j] 的值保持不变，仍然是只考虑前 $i-1$ 个工作时的最优值。
   • 选择工作 $i$: 这只有在我们可以安排工作 $i$ 使其在时间 $j$ 或之前完成，并且满足其自身的截止时间 $d_i$ 时才有可能。如果我们选择工作 $i$，并且让它成为在这个时间点 $j$ 完成的最后一项工作（或者说，该工作是使得总完成时间达到 $j$ 的那个），那么它必须在 $d_i$ 之前完成，所以 $j \le d_i$。同时，执行这项工作需要 $t_i$ 的时间，所以在这项工作开始之前，其他已选的工作必须在 $j - t_i$ 时刻或之前完成。此时能获得的最大报酬是 dp[j - t_i] + p_i。

5. 0/1 背包优化: 结合 0/1 背包的思想，我们可以使用一维 dp 数组。为了避免在一个工作 $i$ 的决策中重复使用工作 $i$ 本身（即防止一个工作被多次计入），我们需要逆序遍历时间 $j$。

   • 对于排序后的第 $i$ 个工作 $(t_i, d_i, p_i)$：
   • 我们从最大的可能完成时间开始向下遍历 $j$。最大的可能完成时间可以是所有 $d_i$ 的最大值，或者是所有 $t_i$ 的总和，在这个问题中，所有 $d_i \le 5000$，所以我们可以将时间上限设为 5000 左右。
   • for j = d_i down to t_i: （注意循环下界是 $t_i$，因为完成时间至少是 $t_i$）
     • dp[j] = max(dp[j], dp[j - t_i] + p_i)

6. 对代码的理解: 提供的代码实现与上述思路略有不同，但本质是相似的。

   • vector<int> dp(5010); 定义 dp[j] 为在时间 $j$ 或之前可以完成的工作获得的最大报酬。
   • sort(e.begin() + 1, e.end()); 按截止时间 d 排序。
   • for (int i = 1; i <= n; i ++ ) { ... } 遍历按截止时间排序后的工作。
   • auto [x, y, z] = e[i]; 获取当前工作的 $t_i=x, d_i=y, p_i=z$。
   • if (x > y) continue; 如果工作时间超过截止时间，该工作不可能完成，跳过。
   • for (int j = 5000; j >= x; j -- ) { ... } 逆序遍历时间 $j$。这里 $j$ 代表的是一个潜在的完成时间点。
   • dp[j] = max(dp[j], dp[min(j, y) - x] + z); 这是核心转移方程。
     • dp[j] 的当前值代表不选工作 $i$ 且完成时间 $\le j$ 的最大报酬。
     • dp[min(j, y) - x] + z 代表选工作 $i$ 的情况。
     • 为什么是 min(j, y)？因为工作 $i$ 必须在它的截止时间 $y$ 之前完成。同时，我们正在考虑更新 $j$ 时刻的 dp 值，这意味着我们关注的是在 $j$ 时刻或之前完成的情况。如果我们将工作 $i$ 安排为当前考虑的组合中的最后一项，并且希望它对 $dp[j]$ 产生贡献，那么它的实际完成时间点 $j’$ 必须满足 $j’ \le j$ 和 $j’ \le y$。所以，最晚的可能完成时间点是 $\min(j, y)$。
     • 如果工作 $i$ 在 $\min(j, y)$ 完成，那么它之前的所有工作的完成时间必须 $\le \min(j, y) - x$。这些工作的最大报酬由 dp[min(j, y) - x] 给出。
     • 因此，选择工作 $i$ 并让它（可能）影响到 $j$ 时刻及之后状态的最大报酬是 dp[min(j, y) - x] + z。
     • 我们用这个值来更新 dp[j]，因为一个在 $\min(j,y)$ 时刻完成的方案也是一个在 $j$ 时刻完成的方案。

7. 最终答案: 经过处理所有 $N$ 个工作后，dp[j] 存储了在时间 $j$ 或之前完成工作的最大报酬。由于我们希望获得整体的最大报酬，而完成时间越晚可能包含越多的工作（但也可能因为错过 deadline 而减少），最终的最大报酬应该是所有可能完成时间点对应的 dp 值中的最大值。因为 dp[j] 的定义是“不超过 j 时刻”，所以 dp[j] 应该是关于 j 单调不减的。因此，最大值一定在最大的时间点 dp[5000] 处取得。

时间复杂度

• 排序：$O(N \log N)$。
• 动态规划：外层循环 $N$ 次，内层循环最多 $D_{max}$ (或 $T_{max} \approx 5000$) 次。总共 $O(N \times D_{max})$。
• 整体复杂度：$O(N \log N + N \times D_{max})$。
  对于 $N=5000, D_{max}=5000$，复杂度约为 $O(5000 \times 5000) = 2.5 \times 10^7$，可以在时限内完成。

空间复杂度

$O(D_{max})$，用于存储 DP 数组。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (虽然本题报酬用 int 足够)

// 定义工作结构体，包含时间 t, 截止时间 d, 报酬 p
struct node {
    int t, d, p;
    // 重载小于运算符，用于按截止时间 d 升序排序
    bool operator<(const node &other) const {
        return d < other.d;
    }
};

// 解决单组测试数据的函数
void solve() {
    int n; // 工作数量
    cin >> n;

    vector<node> e(n + 1); // 存储工作信息 (使用 1-based 索引方便一点)
    for (int i = 1; i <= n; i ++ ) {
        int t, d, p;
        cin >> t >> d >> p;
        e[i] = {t, d, p};
    }
    // 按截止时间 d 升序排序
    sort(e.begin() + 1, e.end());

    // dp[j] 表示考虑了前 i 个任务后，所有选定任务的总完成时间不超过 j 时，能获得的最大报酬
    // 时间上限取 5000 即可，因为截止时间最大为 5000
    // 注意：dp 数组大小设为 5010 避免可能的边界问题
    vector<int> dp(5010, 0); 

    // 遍历按截止时间排序后的每个工作
    for (int i = 1; i <= n; i ++ ) {
        // 获取当前工作的信息: t=x, d=y, p=z
        auto [x, y, z] = e[i];

        // 剪枝：如果工作所需时间大于其截止时间，则不可能完成，跳过
        if (x > y) {
            continue;
        }

        // 逆序遍历时间 j，从最大可能的完成时间 (5000) 到当前工作所需时间 x
        // 这是 0/1 背包优化的关键，确保 dp[j-x] 使用的是考虑前 i-1 个工作时的状态
        for (int j = 5000; j >= x; j -- ) {
            // 尝试将工作 i 加入调度
            // 如果选择工作 i，它最晚可以在 min(j, y) 完成
            //   (必须 <= j 因为我们在计算 dp[j]；必须 <= y 因为 y 是工作 i 的截止时间)
            // 如果工作 i 在 min(j, y) 完成，那么它之前的工作必须在 min(j, y) - x 之前完成
            // 这些之前工作的最大报酬是 dp[min(j, y) - x]
            // 所以，选择工作 i 得到的总报酬是 dp[min(j, y) - x] + z
            // dp[j] 取 "不选工作 i" (原来的 dp[j]) 和 "选工作 i" 两种情况的最大值
            dp[j] = max(dp[j], dp[min(j, y) - x] + z);
        }
    }
    // 所有工作处理完毕后，dp[5000] 存储了在时间 5000 或之前完成工作的最大报酬
    // 由于 dp[j] 是单调不减的，dp[5000] 就是所有可能完成时间中的最大报酬
    cout << dp[5000] << "\n";
}

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; // 数据组数
    cin >> t;

    // 处理每组数据
    while (t -- ) {
        solve();
    }    

    return 0; // 程序正常结束
}