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
#include
#include
#include
#include
#include
#include
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 <<": "<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！