#4631 疯狂的火神

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

输入
第一行一个正整数T，表示数据组数。
对于每组数据，第一行为两个正整数 n 和t，表示跟火神单挑的人的个数和 火神的训练时间。下面 n 行，每行三个正整数 Ai,Bi,Ci，表示每个人的价值，含义见题目。

输出
对于每组数据输出一行一个整数，表示火神最多能得到多少经验值。

样例输入
1
4 10
110 5 9
30 2 1
80 4 8
50 3 2

样例输出
88

数据规模与约定
对于 20%的数据满足：$1\le n\le 10$
对于 50%的数据满足：$1\le n\le 18$
对于 100%的数据满足：$1\le n\le 1000,1\le t\le 3000,1\le Ci\le t,Ai\le 10^6$
保证$n>200$的数据组数不超过 $5$ 组，其他的数据组数不超过 $10$ 组
保证每个人贡献的经验值到训练结束都不会变成负数

SOL
显然的一个背包，但不幸的是你要考虑物品放入顺序——在这道题中，与每个人单挑的时间会直接影响到答案，也就是说，按照不同的更新顺序更新$1...n$，最终答案是不一样的。
考虑到数据规模，你必须像普通背包一样在$O(N\ast M)$的复杂度下维护答案，你需要贪心一个更新顺序，而这个顺序其实是很容易想到的（考场想到却又没写，这可能是我这个远古蒟蒻的日常沙雕行为）：
对于两个人$x，y$，如果$x$先于$y$是更优的，那么对于一个时间$t$，你很容易发现$x，y$的贡献之和在两种情况下的表达式有不同的项：$b[y]\ast c[x]和b[x]\ast c[y]$（计算过程略，其实不算也看的出来（逃））所以要$x$先于$y$更优，则$b[y]\ast c[x]<b[x]\ast c[y]$，于是就有排序标准了！

代码：

#include<bits/stdc++.h>
using namespace std;
#define re register
#define int long long
namespace Base{
	template<typename T>inline void chmax(T &a,T b){return a>b?a:b;}
}using namespace Base;
inline int rd(){
    int re data=0,w=1; char ch=0;ch=getchar();
    while(ch!='-'&&!isdigit(ch))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))data=(data<<3)+(data<<1)+(ch^48),ch=getchar();
    return data*w;
}
inline void write(int x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
const int N=3005;
int T,n,ans,t,f[N];
struct node{int a,b,c;}p[N];
inline bool cmp(const node&A,const node&B){return A.c*B.b<A.b*B.c;}
signed main(){
//	freopen("crazy.in","r",stdin);
//	freopen("crazy.out","w",stdout);
	T=rd();
	while(T--){
		n=rd(),t=rd(),ans=0;
		for(int re i=1;i<=n;i++)p[i].a=rd(),p[i].b=rd(),p[i].c=rd();	
		memset(f,0,sizeof(f));
		sort(p+1,p+n+1,cmp);
		for(int re i=1;i<=n;i++)
			for(int re j=t;j>=p[i].c;j--)
				f[j]=max(f[j],f[j-p[i].c]+p[i].a-p[i].b*j),ans=max(ans,f[j]);
		write(ans),putchar('n');
	}return 0;
}

最后

以上就是仁爱春天为你收集整理的[FROM WOJ]#4631 疯狂的火神#4631 疯狂的火神的全部内容，希望文章能够帮你解决[FROM WOJ]#4631 疯狂的火神#4631 疯狂的火神所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。