二刷提高课,题解目录在这里— 提高课的题解目录
这一题的难点是不仅要考虑吃或不吃,还要考虑吃的顺序
但显然如果直接去看的话,吃的顺序范围是很大的(吃哪一个都有可能)
那么如何才能使得吃的更多(损失的更少呢)
我们选取两块能量石,s1 e1 l1 s2 e2 l2
我们如果吃这两块获得一定是 e1+e2-(损失的能量)
可知第一块后吃损失的能量为:s2* e1 第二块后吃损失:s1*e2
所以只有当s2*e1<s1*e2
时我们才选择先吃第一块
s2*e1<s1*e2 -->s2/e2<s1/e1
也就是si/ei越大我们越先吃,所以我们先进行排序
这样就使得无限得吃顺序变得固定起来,然后我们在进行01背包吃或不吃即可
注意这里只有时间确定了我们才能知道能量消耗了多少,所以状态表示为恰好时间为j
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=10010;
int f[N];
struct ran
{
int s,e,l;
bool operator <(const ran &w)const
{
return s*w.e>e*w.s;//不适用除法有精确度导致的误差
}
}rak[110];
int main()
{
int t;
cin>>t;
int wq=1;
while(t--)
{
int n;
cin>>n;
int m=0;
memset(f,-0x3f,sizeof f);
f[0]=0;
for(int i=0;i<n;i++)
{
int a,b,c;
cin>>a>>b>>c;
rak[i]={a,b,c};
m+=a;
}
sort(rak,rak+n);
for(int i=0;i<n;i++)
{
for(int j=m;j>=rak[i].s;j--)
{
f[j]=max(f[j],f[j-rak[i].s]+(rak[i].e-(j-rak[i].s)*rak[i].l));
}
}
int res=0;
for(int i=1;i<=m;i++)res=max(res,f[i]);
cout<<"Case #"<<wq<<": "<<res<<endl;
wq++;
}
}
这个代码wa了