生活随笔
收集整理的這篇文章主要介紹了
宝箱
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
uva12325
分類枚舉的方法，我們可以根據S1和S2的范圍大小而采取不同的枚舉方法。
1.當N/s2（N/s1）的值較小時，枚舉s2(s1)的個數
2.否則，根據s2v1和s1v2來選擇枚舉S1或者S2；
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int t,n,s1,v1,s2,v2;scanf("%d",&t);for(int tt=1; tt<=t; tt++){//輸入體積為n的箱子，和寶物1的體積、價值以及寶物2的體積、價值。scanf("%d%d%d%d%d",&n,&s1,&v1,&s2,&v2);//性價比=價/量if(s1>s2){swap(s1,s2);swap(v1,v2);}printf("Case #%d: ",tt);//此時s2肯定是比s1大的，但若如此n/s2都大于65536的話，說明//不管是枚舉寶物1還是寶物2的時間復雜度都是很大的！long long value=0;if(n/s2>=65536)// 當n/s1和n/s2都非常大的時候{for(long long i=0; i<=s1; i++)value=max(value,v2*i+(n-i*s2)/s1*v1);for(long long i=0; i<=s2; i++)value=max(value,v1*i+(n-i*s1)/s2*v2);}else//因為數據交換的原因，s2要大些，所以n/s2要小些，此時枚舉寶物2的個數{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;
}
總結
以上是生活随笔為你收集整理的宝箱的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
