AcWing 734. 能量石
#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>using namespace std;const int N = 500007;struct node{int s, e, l;bool operator<(const node &t)const {return s * t.l < t.s * l;}}a[N];int f[N];int n, m, T;int main(){int cnt = 0;scanf("%d", &T);while(T -- ){memset(f, 0xcf, sizeof f);scanf("%d", &n);m = 0;for(int i = 1; i <= n; ++ i){scanf("%d%d%d", &a[i].s, &a[i].e, &a[i].l);m += a[i].s; }sort(a + 1, a + 1 + n);f[0] = 0;for(int i = 1; i <= n; ++ i)for(int j = m; j >= a[i].s; -- j){f[j] = max(f[j], f[j - a[i].s] + max(0, a[i].e - (j - a[i].s) * a[i].l));}int ans = 0;for(int i = 1; i <= m; ++ i)ans = max(ans, f[i]);printf("Case #%d: %d\n", ++cnt, ans);}return 0;}
例题：国王游戏，耍杂技的牛
