UVA12325Zombie's Treasure Chest 宝箱

题意：给定两个箱子体积s1,s2，价值v1,v2，给出一个体积为V的宝箱，求可装入的最大价值。

分析：正常写肯定是超时的，把状况简化，第一种，当s1,s2都很小时，就看它们的价值比，v1/s1 ，v2/s2当v1/s1>v2/s2时，就说明v1的价值更大，更多的搜索v1，v2宝箱最多搜索s1个。下面同理。

第二种，当s1，s2都很大，s1>s2时，优先搜索s1，s1很快就能搜索完。

代码部分：

#include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<iostream> #include<vector> #include<list> using namespace std; typedef long long LL; int s1, s2, v1, v2,M; int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin>>M >> s1 >> v1 >> s2 >> v2;LL curM = 0;if (s1 < s2) {int temp = s1;s1 = s2;s2 = temp;temp = v1;v1 = v2;v2 = temp;}if (M/s1>=65536) {for (LL j = 0; j <= s1; j++) {curM = max(curM, j*v2 + ((M - j * s2) / s1)*v1);}for (LL j = 0; j <= s2; j++) {curM = max(curM, j*v1 + ((M - j * s1) / s2)*v2);}}else {for (LL j = 0; s1*j<=M; j++) {curM = max(curM, j*v1 + ((M - j * s1) / s2)*v2);}}cout << "Case #" << i <<": "<<curM<< endl;}//system("pause");return 0; }

 

总结

以上是生活随笔为你收集整理的UVA12325Zombie's Treasure Chest 宝箱的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。