UVa 12325 - Zombie's Treasure Chest（暴力枚举＋预处理）

发表于 分类于 ， Disqus：

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

首先进行预处理，使n/s1的值尽可能小，满足O(n)的时间不超时。s2的宝物1与s1个宝物2体积相同，所以s=s1s2的体积只会拿宝物s1或s2中的一种（ 当s2v1>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博客，格式可能有所偏差。 **

相关文章