能量石
题意
岩石怪物杜达生活在魔法森林中，他在午餐时收集了 N 块能量石准备开吃。
由于他的嘴很小，所以一次只能吃一块能量石。
能量石很硬，吃完需要花不少时间。
吃完第 i 块能量石需要花费的时间为 Si 秒。
杜达靠吃能量石来获取能量。
不同的能量石包含的能量可能不同。
此外，能量石会随着时间流逝逐渐失去能量。
第 i 块能量石最初包含 Ei 单位的能量，并且每秒将失去 Li 单位的能量。
当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。
能量石中包含的能量最多降低至 0。
请问杜达通过吃能量石可以获得的最大能量是多少？
思路
先贪心得考虑：
假设已经排好吃的顺序了 现在有两个相邻的石头分别是i,i+1
代码
#include <bits/stdc++.h> //#define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); i >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } const int N = 150; int n; int f[10009]; struct Node { int s, e, l; bool operator< (const Node &w) const { return s * w.l < w.s * l; } }stone[N]; void solve(int t) { cin >> n; int m = 0; for (int i = 1; i <= n; ++i) { cin >> stone[i].s >> stone[i].e >> stone[i].l; m += stone[i].s; } memset(f, -0x3f, sizeof f); f[0] = 0; sort(stone + 1, stone + 1 + n); for (int i = 1; i <= n; ++i) { int s = stone[i].s, e = stone[i].e, l = stone[i].l; for (int j = m; j >= s; --j) { // 如果吃当前能量石 那么应该从 j - s 开始吃 // 那么当前能量石就会损失 (j - s) * l 的能量 f[j] = max(f[j], f[j - s] + e - (j - s) * l); } } int res = 0; for (int i = 0; i <= m; ++i) { res = max(res, f[i]); } printf("Case #%d: ", t, res); } signed main() { int t;cin >> t; while(t--) solve(t); return 0; }
