Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5006Accepted Submission(s): 1032
Problem Description
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.
Input
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.
Output
For each test case, output a single line containing the case number and the maximum total value of all items that the warriors can carry with the chest.
Sample Input
2100 1 1 2 2100 34 34 5 3
Sample Output
Case #1: 100Case #2: 86
Source
已知s s1 v1 s2 v2; 设有 x 个 s1 和 y 个 s2 ；满足 x*s1+y*s2<=s 求 max(x*v1+y*v2)
如果直接枚举 0 至 s/s1 可定超时所以可以减减枝，由于LCM(s1,s2)*k==x*s1+y*s2总存在这样的解；
故只需枚举s%LCM(s1,s2)即可;但是要注意了考虑是否存在亏损可以枚举s%LCM(s1,s2)+LCM(s1,s2)至于为毛要加上一个LCM,主要是最后剩下一个小于LCM的空间，这个空间跟一个LCM空间组合，比起两部分拆开分开考虑，可能会有更好的结果，那么为毛不是两个LCM，这是玄学其实，当1+2已经得到最优，，1+2+1最后那个部分单独考虑就行了，因为1+2最优时，肯定已经放不下了，再+1组合考虑跟分开考虑是一样的，因为放不下了呀#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<iostream>#include<algorithm>#include<bitset>#include<climits>#include<list>#include<iomanip>#include<stack>#include<set>using namespace std;typedef long long ll;ll gcd(ll one,ll two){return two==0?one:gcd(two,one%two);}ll lcm(ll one,ll two){return one*two/gcd(one,two);}int main(){int T;cin>>T;for(int cs=1;cs<=T;cs++){ll c,hr,hb,wr,wb;cin>>c>>wr>>hr>>wb>>hb;ll x=lcm(wr,wb),ans,len;if(c<x){ans=0;len=c;}else{ans=(c/x-1)*max(x/wr*hr,x/wb*hb);len=c%x+x;}if(wr<wb){swap(wr,wb);swap(hr,hb);}ll t1=0;for(ll i=0;wr*i<=len;i++){ll t2=i*hr+(len-i*wr)/wb*hb;t1=max(t1,t2);}cout<<"Case #"<<cs<<": "<<ans+t1<<endl;}}
要铭记在心;每天都是一年中最美好的日子
