算法
(贪心+DP) O(T * N * ∑si)
这道题刚开始看的时候很容易让人联想到01背包问题,但如果仅仅这样是错误的。01背包问题仅仅只是一种求组合的问题,只用01背包的思路得到的答案只是在题目样例输入顺序的情况下应当选的组合。而这到题是一个排列问题,前面选的能量石消化时间越长,后面能量石蕴含的能量越少,所以我们需要先用贪心进行排序,当排完序后,这到题就变成了组合问题,可以用01背包的思路求解了。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10010,M=110;
int T,n;
int s,e,l;
int f[N];
struct Stone{
int s,e,l;
bool operator < (const Stone &w)const{
return s*w.l<w.s*l;
}
}stone[M];
int main(){
cin>>T;
for(int c=1;c<=T;c++){
memset(f,0xcf,sizeof f);
f[0] = 0;
cin>>n;
int t=0;
for(int i=0;i<n;i++){
cin>>s>>e>>l;
stone[i] = {s,e,l};
t += s;
}
sort(stone,stone + n);
for(int i=0;i<n;i++){
s = stone[i].s;
e = stone[i].e;
l = stone[i].l;
for(int j = t;j>=s;j--)
f[j] = max(f[j],f[j-s]+max(0,e-(j-s)*l));
}
int res = 0;
for (int i = 0; i <= t; i ++ ) res = max(res, f[i]);
printf("Case #%d: %d\n",c,res);
}
}