好题！一开始看到题觉得和之前做过的很像，就三分然后wa了。
这题需要好好思考！考虑去枚举操作。
当某一种的最多可拿数量 <= 1e5时，我们可以直接枚举这一种取多少个。
当两种的最多可拿数量都 > 1e5时，这时很显然的是s1,s2都很小，那么我们的枚举范围需要压到和s1,s2线性相关，这样复杂度就比较低。
我们可以把这两个物品考虑成单位重量的物品，这样可以比较两者的性价比，即v1 / s2 与 v2 / s1的大小。
当v1 / s1 >= v2 / s2即 v1 * s2 >= v2 * s1时，此时，如果要放s1 个 v2 显然替换成s2 个 v1性价比更高，这里为什么性价比更高？
因为v1 * s2 >= v2 * s1，所以v2最多只会放置s1 - 1个，那么我们枚举v2的个数即可。
反之，v1最多只会放置s2 - 1个，那么枚举v1的个数即可。
输入会爆int，全都用longlong了。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5+5; const int M = 1e4+5; const LL Mod = 1e9+7; #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < ‘0‘ || c > ‘9‘){if(c == ‘-‘) f = -1;c = getchar();} while(c >= ‘0‘ && c <= ‘9‘){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; int main() { int ca;ca = read(); int lim = 100000; int tot = 0; while(ca--) { LL n,s1,v1,s2,v2;n = read(),s1 = read(),v1 = read(),s2 = read(),v2 = read(); LL up1 = n / s1,up2 = n / s2; LL ans = 0; if(up1 <= lim) { for(LL i = 0;i <= up1;++i) { LL ma = 1LL * i * v1 + 1LL * (n - i * s1) / s2 * v2; ans = max(ans,ma); } } else if(up2 <= lim) { for(LL i = 0;i <= up2;++i) { LL ma = 1LL * i * v2 + 1LL * (n - i * s2) / s1 * v1; ans = max(ans,ma); } } else { LL tmp1 = s1 * v2,tmp2 = s2 * v1; if(tmp1 >= tmp2) { for(LL i = 0;i < s2;++i)//v1最多s2 - 1 { ans = max(ans,i * v1 + (n - i * s1) / s2 * v2); } } else { for(LL i = 0;i < s1;++i)//v2最多s1 - 1 { ans = max(ans,i * v2 + (n - i * s2) / s1 * v1); } } } printf("Case #%d: %lld\n",++tot,ans); } system("pause"); return 0; }
《3816: Zombie’s Treasure Chest》
原文：https://www.cnblogs.com/zwjzwj/p/14099629.html
