HDU-4091 Zombie’s Treasure Chest(暴力)

传送门

思路：直接暴力枚举会TLE，先计算s1 s2的LCM，分两种情况讨论。

1.n<lcm 直接枚举

2.n>=lcm 先求r=n%lcm，将n分为两部分，n-r-lcm和r+lcm，第一部分直接计算，第二部分暴力枚举。

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

int main()
{
    int ww;
    scanf("%d",&ww);
    for (int ca=1; ca<=ww; ca++)
    {
        long long n,s1,v1,s2,v2;
        scanf("%lld%lld%lld%lld%lld",&n,&s1,&v1,&s2,&v2);
        long long ans=0;
        if (s1<s2)
        {
            swap(s1,s2);
            swap(v1,v2);
        }
        long long g=__gcd(s1,s2);
        long long lcm=s1*s2/g;
        long long r=n%lcm;
        if (n<lcm)
        {
            int p=0;
            while (p*s1<=n)
            {
                ans=max(ans,p*v1+(n-p*s1)/s2*v2);
                p++;
            }
        }
        else
        {
            long long tmp=(n-r-lcm)/lcm*max(lcm/s1*v1,lcm/s2*v2);
            int p=0;
            while (p*s1<=lcm+r)
            {
                ans=max(ans,tmp+p*v1+(lcm+r-p*s1)/s2*v2);
                p++;
            }
        }
        printf("Case #%d: %lld\n",ca,ans);
    }
    return 0;
}