首页 > 代码库 > hdu 4091 Zombie’s Treasure Chest 贪心+枚举
hdu 4091 Zombie’s Treasure Chest 贪心+枚举
转自：http://blog.csdn.net/a601025382s/article/details/12308193
题意：
输入背包体积n，绿宝石体积s1，价值v1，蓝宝石体积s2，价值v2，宝石数目无限，问背包里能放下的最大价值？
题解：
看过去很像完全背包，可数据很大(虽然没给出，也能猜到，不然太水了)，所以不能用背包求。又只有两种物品，想到了贪心，将价值与体积比大(称为价值比)的优先放入。但体积限制，这样还不可以，还需要枚举减少价值比大的宝石个数，是否可以增大所求价值。又我们可以知道对于体积是m=lcm(s1,s2)背包，肯定全选价值比大的。所以至多只要枚举n-n/m+m的体积。如果小于这个值，存在大于m的空余，这个空余肯定用价值大的放置。
注意：
1.不够一个公倍数的时候，计算需要小心。。我就出错了。。
2.枚举的时候，跨度选择max（s1,s2），这个算是优化吧，没有的话会TLE
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<set> 10 #include<string> 11 //#include<pair> 12 13 #define N 10000005 14 #define M 1005 15 #define mod 1000000007 16 //#define p 10000007 17 #define inf 0x3f3f3f3f 18 #define mod2 100000000 19 #define ll long long 20 #define LL long long 21 #define maxi(a,b) (a)>(b)? (a) : (b) 22 #define mini(a,b) (a)<(b)? (a) : (b) 23 24 using namespace std; 25 26 ll n,s1,v1,s2,v2; 27 ll ans; 28 ll ma; 29 ll g; 30 ll c1,c2; 31 ll ans1,ans2; 32 33 ll gcd(ll a,ll b) 34 { 35 return b==0?a:gcd(b,a%b); 36 } 37 ll lcm(ll a,ll b) 38 { 39 return a/gcd(a,b)*b; 40 } 41 42 void ini() 43 { 44 ans=0; 45 ans1=ans2=0; 46 scanf("%I64d%I64d%I64d%I64d%I64d",&n,&s1,&v1,&s2,&v2); 47 g=lcm(s1,s2); 48 c1=g/s1; 49 c2=g/s2; 50 } 51 52 53 54 void solve() 55 { 56 if(n/g>=1) 57 ans1=(n/g-1)*max(c1*v1,c2*v2); 58 ll i; 59 if(s1<s2){ 60 swap(c1,c2); 61 swap(s1,s2); 62 swap(v1,v2); 63 } 64 ll left=n%g; 65 if(n/g>=1) 66 left+=g; 67 ll en=left/s1; 68 ll re; 69 for(i=0;i<=en;i++){ 70 re=i*v1+(left-i*s1)/s2*v2; 71 ans2=max(ans2,re); 72 } 73 ans=ans1+ans2; 74 } 75 76 void out() 77 { 78 printf("%I64d\n",ans); 79 } 80 81 int main() 82 { 83 int T; 84 //freopen("data.in","r",stdin); 85 //freopen("data.out","w",stdout); 86 scanf("%d",&T); 87 for(int ccnt=1;ccnt<=T;ccnt++) 88 // while(T--) 89 // while(scanf("")) 90 { 91 //if(n==0 && k==0 ) break; 92 93 ini(); 94 solve(); 95 printf("Case #%d: ",ccnt); 96 out(); 97 } 98 99 return 0;100 }
hdu 4091 Zombie’s Treasure Chest 贪心+枚举
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。