hdu 4091 Zombie’s Treasure Chest(数学规律+枚举)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4091

/** 这题的一种思路就是枚举了：
基于这样一个事实：求出lcm = lcm(s1,s2), num1 = lcm/s1, num2 = lcm/s2;  则价值与体积比小的那个宝藏个数一定大于lcm/size;这个用反证法就可证明。
然后就是只需要枚举N%lcm + lcm这个体积的最有分配。 

*/

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

long long N,s1,v1,s2,v2;
long long ans;

long long gcd(long long a,long long b)
{
    if(a < b) swap(a,b);
    if(b == 0) return a;
    return  gcd(b,a%b);
}

int main()
{
    //freopen("E:\acm\input.txt","r",stdin);

    int T;
    cin>>T;

    for(int cas=1; cas<=T; cas++)
    {
        ans = 0;
        scanf("%I64d %I64d %I64d %I64d %I64d",&N,&s1,&v1,&s2,&v2);
        
        if(v1*s2 < v2*s1)
        {
            swap(v1,v2);
            swap(s1,s2);
        }
        
        long long lcm = s1*s2/gcd(s1,s2);
        long long res = N%lcm+lcm;
        ans = (N-res)/s1 * v1;  
        
        if(N <= lcm)
        {
            ans = 0;
            res = N;
        }  //特殊情况，就特殊处理下

        int lim = res/max(s1,s2);  
        long long temp = 0;
        for(int i=0; i<=lim; i++)
        {
            int k = (res-i*s1)/s2;
            temp = max(temp,i*v1+k*v2);
            k = (res-i*s2)/s1;
            temp = max(temp,i*v2+k*v1);
        }

        printf("Case #%d: %I64d
",cas,ans+temp);
    }
}