# HDU 4091-Zombie’s Treasure Chest-贪心-[解题报告]HOJ

2016-03-14 15:01:27来源:[db:出处]作者:[db:作者]人点击

Zombie’s Treasure Chest

Some brave warriors come to a lost village. They are very lucky and find a lot of treasures and a big treasure chest, but with angry zombies.The warriors are so brave that they decide to defeat the zombies and then bring all the treasures back. A brutal long-drawn-out battle lasts from morning to night and the warriors find the zombies are undead and invincible.Of course, the treasures should not be left here. Unfortunately, the warriors cannot carry all the treasures by the treasure chest due to the limitation of the capacity of the chest. Indeed, there are only two types of treasures: emerald and sapphire. All of the emeralds are equal in size and value, and with infinite quantities. So are sapphires.Being the priest of the warriors with the magic artifact: computer, and given the size of the chest, the value and size of each types of gem, you should compute the maximum value of treasures our warriors could bring back.

There are multiple test cases. The number of test cases T (T <= 200) is given in the first line of the input file. For each test case, there is only one line containing five integers N, S1, V1, S2, V2, denoting the size of the treasure chest is N and the size and value of an emerald is S1 and V1, size and value of a sapphire is S2, V2. All integers are positive and fit in 32-bit signed integers.

There are multiple test cases. The number of test cases T (T <= 200) is given in the first line of the input file. For each test case, there is only one line containing five integers N, S1, V1, S2, V2, denoting the size of the treasure chest is N and the size and value of an emerald is S1 and V1, size and value of a sapphire is S2, V2. All integers are positive and fit in 32-bit signed integers.

2100 1 1 2 2100 34 34 5 3

Case #1: 100Case #2: 86

1.不够一个公倍数的时候，计算需要小心。。我就出错了。。

2.枚举的时候，跨度选择max（s1,s2），这个算是优化吧，没有的话会TLE

#include #include #include #include #include using namespace std;typedef __int64 LL;LL gcd(LL a,LL b){ return b==0?a:gcd(b,a%b);}LL lcm(LL a,LL b){ return a/gcd(a,b)*b;}int main(){ LL n,s1,v1,s2,v2; LL T,tt=0; cin>>T; while(T--) { LL i,j,k,ans,p,q,m,num; cin>>n>>s1>>v1>>s2>>v2; m=lcm(s1,s2); num=n/m; if(num){num--;} if(v1*s2>=v2*s1) { num=m/s1*num; p=(n-num*s1)/s2; ans=num*v1+p*v2; if(s1>=s2) { for(i=num;i*s1<=n;i++) { q=i*v1+(n-i*s1)/s2*v2; if(q>ans)ans=q; } } else { for(i=p;i>=0;i--) { q=i*v2+(n-i*s2)/s1*v1; if(q>ans)ans=q; } } } else { num=m/s2*num; p=(n-num*s2)/s1; ans=num*v2+p*v1; if(s2>=s1) { for(i=num;i*s2<=n;i++) { q=i*v2+(n-i*s2)/s1*v1; if(q>ans)ans=q; } } else { for(i=p;i>=0;i--) { q=i*v1+(n-i*s1)/s2*v2; if(q>ans)ans=q; } } } cout<<"Case #"<<++tt<<": "< 