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

本文主要是介绍【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$ 更优时）：
$a_p-b_p(T+c_p)+a_q-b_q(T+c_p+c_q)>a_q-b_q(T+c_q)+a_p-b_q(T+c_q+c_p)$
（其中 $T$ 表示前面所用时间）
那我们化简一下，发现原式变成了： $\dfrac{c_p}{b_p}<\dfrac{c_q}{b_q}$

那么显然，按照 $\dfrac{c_i}{b_i}$ 从小到大取肯定是最优的。

于是，我们把 $c_i$ 看做空间，那么剩下的就是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);}
}