- #include
- #include
- #include
- using namespace std;
- int main()
- {
- //freopen("in.txt","r",stdin);
- //freopen("ans.txt","w",stdout);
- int t,n,s1,v1,s2,v2;
- scanf("%d",&t);
- for(int tt=1; tt<=t; tt++)
- {
- scanf("%d%d%d%d%d",&n,&s1,&v1,&s2,&v2);
- if(s1>s2)
- {
- swap(s1,s2);
- swap(v1,v2);
- }//s1 must bigger than s2
- printf("Case #%d:",tt);
- long long value=0;
- if(n/s2>=65536)
- {
- for(long long i=0; i<=s1; i++)//2
- value=max(value,v2*i+(n-i*s2)/s1*v1);
- for(long long i=0; i<=s2; i++)//1
- value=max(value,v1*i+(n-i*s1)/s2*v2);
- }
- else
- {
- for(long long i=0; s2*i<=n; i++)
- value=max(value,v2*i+(n-s2*i)/s1*v1);
- }
- printf("%lld\n",value);
- }
- return 0;
- }
其实, 当一个一个枚举的时候, 可以这样想, 当我的某一种比较小的时候就可以枚举他.
但是要是 s1,s2 都很小的时候, 枚举哪个都是超时的.
这个时候, 可以这样考虑, 假设两中体积相等 (1 宝贝 s2 个, 2 宝贝 s1 个), 但是他有一个性价比, 价值分别是 s2*v1 和 s1*v2;
那么如果 1 宝贝价值大一点, 那么 2 宝贝肯定个数小于 s1 个, 枚举这 s1 个就 OK 了
------------------------------------------------------------------
空间相同, 想要装入更多的价值宝贝, 必须尽量装入性价比高的宝贝
来源: http://www.bubuko.com/infodetail-3398894.html