HDU 4091 Zombie’s Treasure Chest (每日一题)

大意是： 一些战士来到了一个村庄，发现了两种宝石和一个宝箱，每种宝石的个数是无限的，给出了宝箱的大小 N 和两种宝石的 size 和 value ，即 N s1 v1 s2 v2,已知这五个两，求利用这个宝箱，战士能够带走多大价值的宝石。 五个数的范围是 int 。 也就是 10^9。

如果范围比较小的话，就直接可以用多重背包的解法。 但是数据范围是 10^9 就没法用 多重背包来做了。。

在这给出一种数学的解法，非背包的解法。

解：1 。求出 s1,s2 的最小公倍数。最小公倍数等于s1乘以s2 在除以s1和s2在最大公约数即lcm=（s1*s2）/gcd(s1,s2)。

为什么求最小公倍数呢？

会有这么一个性质存在。。a = lcm /s1,b = lcm/s2 。 最小公倍数除以s1 s2 后的到 a,b。 a 个宝石一 和 b 个宝石二 所占的空间是相同的。

于是对于最优解中，单位价值小的宝石取得个数应该小于最大公倍数除以这个宝石体积。也就是说 如果宝石一的单位价值小的话， 那么num1 < a。

证明。设num1>a，那么对于这num1 个宝石 从中取出a个 ，把这a 个换成b个宝石二。由于a个宝石一 跟b个宝石二的所占的体积相同，但宝石二的单位价值更大。所以更换以后的总价值会更大，则num1 的个数应该小于a。

2 。因此我们可以把N 划分成两部分来求 1。intvn = N%lcm +2*lcm。（其实N%lcm +lcm 就够了但不会证明就用了N%lcm+2*lcm了。最效率影响不大） 2。N-vn 这两部分。 对部分二 一定是lcm 的倍数 直接能够求出这部分的最优解。关键是部分一。 为什么划分出部分1呢？ 我们可以单独考虑宝石一小于a 的部分和宝石二小于b的部分。vn 定能覆盖这两部分的体积。

对于vn 这暴力求解。 for from 0 to vn/(max(s1,s2)) 循环大的值，是因为循环次数少，提高效率。这个循环最坏情况大致是10^4 到10^5 。

两部分总价值的就是解。。

（表达不好。。。。。。。。）

附上本人的代码：（注 代码不够优雅，正在努力改正）

#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
int t;
int n,s1,v1,s2,v2;
// 求最大公约数
int gcd(int da,int xiao){
       int temp =0;
        while(xiao!=0){
            temp = da%xiao;
            da =xiao;
            xiao = temp;
        }
        return da;
}

int max(int a,int b){
 return  (a>b)?a:b;
}
// LL　在 define  是long long
LL max2(LL a,LL b){
    return (a>b)?a:b;
}
int min(int a,int b){
  return (a<b)?a:b;
}
LL cal (){
    LL sum = n;
    //answer 为 最大价值  最后返回这个answer
    LL answer = 0;
    //a 为 s1 s2 中的大值,va 为 a 的value
        int  a = max(s1,s2);
        int  b = min(s1,s2);
        int  va,vb;
     if(s1==a){
        va = v1;
        vb = v2;
     }else{
        va = v2;
        vb = v1;
     }
     // 求最小公倍数  。。 返回值 longlong 否则 wa 我一开始就wa 在这
       LL lcm = s2/gcd(a,b)*(LL)s1;
       if(sum>=2*lcm){
           int num = (sum-2*lcm)/lcm;
           answer += num*max2(lcm/s1*v1,lcm/s2*v2);
           sum =sum - num*lcm;
       }
       int  i_max = sum/a;
       LL maxn=0;
       //循环暴力求解
       for(int i=0 ;i<=i_max;i++){
            int j = (sum-i*a)/b;
            LL tmp = i*(LL)va+j*(LL)vb;
            maxn=max2(maxn,tmp);
       }
       answer += maxn;
       return  answer;
}
int main(){
     scanf("%d",&t);
     for(int i=1;i<=t;i++){
         scanf("%d%d%d%d%d",&n,&s1,&v1,&s2,&v2);
         printf("Case #%d: ",i);
         cout << cal()<<endl;
     }
}

这个题目一定要注意 long long 的范围 。。。。。

这个题目某些情况可以特判后提高效率 。比如正好整除的情况 。。。

此题还有其他解法，稍后附上。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!