【BestCoder Round #59 (div.1) B】【JZOJ4693】疯狂的火神

Description

火神为了检验zone的力量，他决定单挑n个人。 由于火神训练时间有限，最多只有t分钟，所以他可以选择一部分人来单挑，由于有丽子的帮助，他得到了每个人特定的价值，每个人的价值由一个三元组(a,b,c)组成，表示如果火神在第x分钟单挑这个人（x指单挑完这个人的时间），他就会得到a-b*x的经验值，并且他需要c分钟来打倒这个人。 现在火神想知道，他最多可以得到多少经验值，由于火神本来就很笨，进入zone的疯狂的火神就更笨了，所以他希望你来帮他计算出他最多可以得到多少经验值。

原题在这里

Solution

这题看起来好像比较棘手，但是套路告诉我们，这应该是贪心。

我们对于两个人 p,q ，什么时候先取 p 更优呢？

我们把式子写出来（当取p更优时）： ap−bp(T+cp)+aq−bq(T+cp+cq)>aq−bq(T+cq)+ap−bq(T+cq+cp) （其中 T 表示前面所用时间） 那我们化简一下，发现原式变成了：cpbp<cqbq

那么显然，按照 cibi 从小到大取肯定是最优的。

于是，我们把 ci 看做空间，那么剩下的就是01背包问题了。

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define N 1001 using namespace std; bool bz[N]; int n,t; int ans=0; int f[2][N*3]; int g[N*3]; struct node{ int a,b,c; }b[N]; bool cmp(node x,node y) { return (x.c*1.0/x.b)<(y.c*1.0/y.b); } int main() { int T; cin>>T; while(T--) { scanf("%d %d",&n,&t); fo(i,1,n) scanf("%d %d %d",&b[i].a,&b[i].b,&b[i].c); sort(b+1,b+n+1,cmp); memset(f,0,sizeof(f)); fo(i,1,n) fo(j,1,t) { f[i%2][j]=f[(i-1)%2][j]; if(j>=b[i].c) f[i%2][j]=max(f[i%2][j],f[(i-1)%2][j-b[i].c]+b[i].a-b[i].b*j); } ans=0; fo(i,1,t) ans=max(ans,f[n%2][i]); printf("%d\n",ans); } }