能量石

AcWing-734-能量石

分析

“恰好”。

实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110, M = 10010;
struct node {
    int s, e, l;
    bool operator < (const node& o) const {
        return s * o.l < l * o.s;
    };
};
int n;
node a[N];
int f[M];

int main () {
    int _;
    cin >> _;
    for (int T = 1; T <= _; ++ T) {
        cin >> n;
        for (int i = 1; i <= n; ++ i) cin >> a[i].s >> a[i].e >> a[i].l;

        int m = 0;
        for (int i = 1; i <= n; ++ i) m += a[i].s;
        sort(a + 1, a + n + 1);
        memset(f, -0x3f, sizeof(f));
        f[0] = 0;
        for (int i = 1; i <= n; ++ i) {
            int s = a[i].s, e = a[i].e, l = a[i].l;
            for (int j = m; j >= s; -- j)
                f[j] = max(f[j], f[j - s] + e - (j - s) * l);
        }

        int res = 0;
        for (int j = 0; j <= m; ++ j)
            res = max(res, f[j]);
        cout << "Case #" << T << ": " << res << endl;
    }
    return 0;
}