算法

排序+01背包

#pragma GCC optimize(2)
#include <bits/stdc++.h>

using namespace std;

const int N = 5010;

struct Node
{
    int t, d, p; // 消耗时间, 必须在d时刻完成,报酬

    bool operator<(const Node &a) const
    {
        if (a.d != d)
            return d < a.d;
        else if (a.t != t)
            return t < a.t;
    }
} a[N];

int n, m;
int f[N];

void solve()
{
    memset(f, 0, sizeof(f));

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int t, d, p;
        cin >> t >> d >> p;

        a[i].t = t;
        a[i].d = d;
        a[i].p = p;
    }

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++)
    {
        for (int j = a[i].d; j >= a[i].t; j--)
        {
            f[j] = max(f[j], f[j - a[i].t] + a[i].p);
        }
    }

    int ans = 0;

    for (int i = 0; i < N; i++)
    {
        ans = max(ans, f[i]);
    }

    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;

    cin >> T;

    while (T-- > 0)
    {
        solve();
    }

    return 0;
}