[FROM WOJ]#4631 疯狂的火神#4631 疯狂的火神

104 阅读 0 评论 69 点赞

我是靠谱客的博主仁爱春天，这篇文章主要介绍[FROM WOJ]#4631 疯狂的火神#4631 疯狂的火神，现在分享给大家，希望可以做个参考。

#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 \leq n \leq 10$
对于 50%的数据满足： $1 \leq n \leq 18$
对于 100%的数据满足： $1≤n≤1000,1≤t≤3000,1≤Ci≤t,Ai≤10^6$
保证 $n > 200$ 的数据组数不超过 $5$ 组，其他的数据组数不超过 $10$ 组
保证每个人贡献的经验值到训练结束都不会变成负数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}