题目分析

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int M = 10010 ,N = 110;
int f[M];
struct Node{
    int s, e, l;
    bool operator < (const Node &x) const{
        return s * x.l < x.s * l;
    }
}a[N];
int n;
int main() {
    int cnt , T;
    cin >> T;
    while (T -- ) {
        cin >> n;
        int t = 0;
        memset(f,-0x3f,sizeof f);
        for (int i = 1 ; i <= n ;i ++ ) {
            int s , e, l;
            cin >> s >> e >> l;
            a[i] = {s,e,l};
            t += s;
        }
        sort(a + 1 , a + 1 + n);
        int res = 0 ;
        f[0] = 0;
        for (int i = 1 ; i <= n ; i ++ ) {
            for (int j = t ; j >= a[i].s ; j -- ) {
                if (a[i].e - (j - a[i].s) * a[i].l >= 0)
                f[j] = max(f[j] , f[j - a[i].s] + a[i].e - (j - a[i].s) * a[i].l);
                res = max(res,f[j]);
            }
        }

         printf("Case #%d: %d\n", ++cnt, res);
    }

    return 0;
}