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

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

Sample Input 1 4 10 110 5 9 30 2 1 80 4 8 50 3 2 Sample Output 88

Data Constraint 对于 20%的数据1≤n≤10 对于50%的数据1≤n≤18 对于100%的数据1≤n≤1000,1≤t≤3000,1≤Ci≤t,Ai≤10^6 保证n>200的数据组数不超过五组，其他的数据组数不超过10组 保证每个人贡献的经验值到训练结束都不会变成负数

分析

看到题目就感觉像01背包，

在有限的时间里面，挑战一些人，使得获得的经验值最大。

但是，挑战每个人获得的经验值与时间相关。

那么如果确定了挑战的顺序，

剩下的东西就可以通过01背包轻松搞定。

但是，这个顺序怎么求？

如果求全排列，那么时间复杂度就是阶乘了，

很显然，会超时。

那么，可能会有一种最优顺序了。

假设我们选择了第i个人和第j个人，

怎样给题目安排顺序呢？

再假设在第m个时刻，第i个人排在第j个人前更优

就有：

ai−bi∗(ci+m)+aj−bj∗(ci+cj+m)＞ai−bi∗(ci+cj+m)+aj−bj∗(ci+m)

化简得：

bj∗ci＜bi∗cj

再移项：

bj÷bi＜cj÷ci

现在我们就得到一个排序的条件。

换一个方面想，也很容易理解。

挑战两个人可以获得的经验值就是 ai+aj

因为在时刻m

所以都要减去 m∗bi+m∗bj

而剩下的影响就是顺序了，

很显然，就是上面的那道式子。

接下来就很简单了，

只需要做一次01背包就可以了。

code(c++)

#include <cstdio> #include <algorithm> #include <cstring> #include <string.h> #include <cmath> #include <stdlib.h> #include <math.h> #define a(i) g[i].a #define b(i) g[i].b #define c(i) g[i].c using namespace std; struct note{ int a,b,c; }g[1001]; int T,n,t,ans; int f[3003]; bool cmp(note x,note y) { return(y.b*x.c<x.b*y.c); } int main() { scanf("%d",&T); while(T) { T--; scanf("%d%d",&n,&t); for(int i=1;i<=n;i++) scanf("%d%d%d",&a(i),&b(i),&c(i)); sort(g+1,g+1+n,cmp); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) for(int j=t;j>=c(i);j--) f[j]=max(f[j],f[j-c(i)]+a(i)-b(i)*j); ans=0; for(int i=1;i<=t;i++) ans=max(ans,f[i]); printf("%d\n",ans); } }