UVa 12325 - Zombie's Treasure Chest(暴力枚举+预处理)

给出背包大小n,两种宝物的体积s1、s2,两种宝物的价值v1、v2。求能装下的最大价值。

首先进行预处理,使n/s1的值尽可能小,满足O(n)的时间不超时。s2的宝物1与s1个宝物2体积相同,所以s=s1s2的体积只会拿宝物s1或s2中的一种(
当s2
v1>s1*v2时,只拿宝物1,反之亦然),这样就把n转化为n%s。然后为了使n/s1尽量小,当s1<s2时,交换s1、s2和v1、v2的值。

然后从零开始枚举需要拿的v1的个数,上限是n/s1,因为进行过预处理,所以保证不会超时。求出与处理之后的最大价值。

最后加上预处理拿到的价值x就是所求答案。

还要注意一点就是,s1、s2、v1、v2的值在int范围内,但相乘之后可能溢出,所以要使用long long。

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
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int k,t=0;
scanf("%d",&k);
while(k--){
long long n,s1,s2,v1,v2,x,best=0;
scanf("%lld%lld%lld%lld%lld",&n,&s1,&v1,&s2,&v2);
long long s=s1*s2,v=max(s2*v1,s1*v2);//求s=s1*s2时的最大价值v。
x=n/s*v;//预处理获得的价值。
n%=s;
if(s1<s2) swap(s1,s2),swap(v1,v2);
for(long long i=0;i<=n/s1;++i){
long long cur=0,m=n;
cur+=i*v1;
m-=i*s1;
cur+=m/s2*v2;
best=max(best,cur);//枚举维护最大价值。
}
best+=x;//二者相加。
printf("Case #%d: %lld\n",++t,best);
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。