WorkPlan

Problem Statement

小 K 有 N 项工作等待完成，第 i 项工作需要花 $t_{i}$ 单位时间，必须在 $d_{i}$ 时刻或之前完成，报酬为 $p_{i}$。假设小 K 工作时刻从 0 开始，且同一时刻只能做一项工作、工作一旦开始则不可中断或切换至其他工作，请你帮小 K 规划一下如何选择合适的工作，使小 K 可以获得最多的报酬。

Input

输入第一行是一个正整数 (T ≤5)，表示数据的组数。

接下来有 T 组数据，每组数据第一行是一个正整数 N (≤5000)，表示待完成工作的数量。接下来的 N 行，每行三个非负整数 $t_{i} d_{i} p_{i}$ (均 ≤5000;1≤i≤N)，表示第 i 项工作需要花费的时间、截止时间以及报酬。

Output

对于每组数据，输出小 K 能获得最多的报酬是多少。

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


struct node
{   
    // 需要时间 截止时间 完成贡献
    int t,d,p;
};
void solve()
{
    int n;
    cin >> n;
    vector<node> a;
    for(int i=0;i<n;i++) 
    {
        int t,d,p;
        cin >> t >> d >> p;
        if (t>d) continue; // 如果需要时间在截止时间之后则无效
        a.push_back({t,d,p});
    }
    n = a.size();
    sort(a.begin(),a.end(),[&](node x, node y)
    {   
        // 贪心
        if (x.d != y.d) return x.d < y.d; // 优先安排截止时间紧迫的任务
        if (x.t != y.t) return x.t < y.t; // 再优先安排花费时间少的任务
        return x.p > y.p; // 最后优先安排贡献多的任务
    });
    vector<int> dp(5010); // dp[i]表示截止至i时间前最多能获得多少报酬
    for (int i=0;i<n;i++)
    {
        auto [t,d,p] = a[i];
        for(int j=d;j>=t;j--) // 0/1背包，当前任务做还是不做 
        {
            dp[j] = max(dp[j], dp[j-t] + p);
        }
    }
    int hi = 0;
    for (int i=0;i<=5000;i++) hi = max(hi,dp[i]);
    cout << hi << endl;
}