传送门

题意:有一个容量为n的箱子,和无限多的两种珠宝,体积和价值分别是s1,v1,s2,v2,求能装下的最大价值。

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

1.n<lcm 直接枚举

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

注意:枚举时使用s1 s2中较大的进行枚举!
#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;
}
Latest posts by 青鸟千秋 (see all)

CF-1025D Recovering BST(区间dp)

传送门 题意:给定n个整数,问是否能生成一棵BST(二分查找树,左子树都比它小,右子树都比它大),并且有边相连的点权的gcd>1。 思路:区间dp,dp[l][...

阅读全文

牛客网暑期多校第五场E room(费用流)

传送门 题意:有n个宿舍,每个宿舍住4个人,给定去年n个宿舍的人员构成,今年n个4人组合的情况,求最少几个人需要搬寝室。 思路:转化为最小费用最大流解...

阅读全文

HDU-6299 Balanced Sequence(贪心)

传送门 题意:有n个字符串,每个字符串仅包含'(‘和’)’,可以按某种方法将这n个字符串连接起来,求最后字符串能完全匹配的子串的长度。 ...

阅读全文

欢迎留言