7-29 587 views
题意:有一个容量为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)
- Ceph客户端缓存一致性分析 - 2019年6月21日
- CephFS:什么是CAPS? - 2019年6月21日
- Ceph集群快速搭建教程 - 2019年6月20日