详细内容请查看注释
参考代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010, M = 110;
struct Stone{
int s, e, l;
bool operator< (const Stone& W) const{
return s * W.l < l * W.s;
}
}stone[M];
int n, m, T, f[N];
/*
贪心 + 01背包:
类似算法基础课贪心最后一题:125. 耍杂技的牛:https://www.acwing.com/problem/content/127/
1. 贪心:
猜想:选择的顺序一定有点问题!
假如我们考虑选择 i 和 i + 1 两个相邻物品!
t表示之前已经经过的时间!
i i + 1
交换前总能量: E[i] - t * L[i] + E[i + 1] - (t + S[i]) * L[i + 1]
i + 1 i
交换后总能量: E[i + 1] - t * L[i + 1] + E[i] - (t + s[i + 1]) * L[i]
我们简化一下不等式看一下什么情况交换前更好:
即:S[i] * L[i + 1] < s[i + 1] * L[i]
或:S[i] / L[i] < S[i + 1] / L[i + 1]
因此我们只要按照上诉排序即可,由于分母L可能为0,因此我们使用乘法排序即可!
2. 01背包:
状态表示:f[i][j]表示只从前i个能量石中选且总体积(总时间)恰好为j的选法集合!属性:最大能量!
状态计算:
01背包标准式子:f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w);
v -> s, w -> 即当前能量石剩余的能量(从开始到现在经过的时间是j - s): (j - s) * l
因此:f[i][j] = max(f[i - 1][j], f[i - 1][j - s] + (j - s) * l);
注意:由于要计算从开始到现在经过的时间,为了方便,将状态表示为恰好为j更加方便!
最终答案:max(f[n][k])(k = 0,1,2,3...m,m为n个能量石的总体积(总时间))
初始化:
1. memset(f, -0x3f, sizeof f):没有计算过的状态都为负无穷,表示未计算!
2. f[0][0] = 0:前0个能量石且总时间为0方案合法,最大能量为0
*/
int main(){
cin >> T;
for(int C = 1; C <= T; C ++){
cin >> n; m = 0;
for(int i = 0; i < n; i ++){
int s, e, l; cin >> s >> e >> l;
stone[i] = {s, e, l};
m += s;
}
sort(stone, stone + n);
memset(f, -0x3f, sizeof f);
f[0] = 0;
for(int i = 0; i < n; i ++){
int s = stone[i].s, e = stone[i].e, l = stone[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]);
printf("Case #%d: %d\n", C, res);
}
return 0;
}