这题刚开始我就贪心，直接wrong了，贪心适合可以取一个物体部分的题。
还是老实枚举吧，注意枚举要分类，不然可能会超时，还有注意答案是long long
AC代码：
#include<cstdio> //贪心会错
#include<algorithm>
using namespace std;
const int maxn=100500; //枚举的最大上限
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
int main() {
int T;
scanf("%d",&T);
int n,s1,v1,s2,v2;
int kase=0;
while(T--) {
scanf("%d%d%d%d%d",&n,&s1,&v1,&s2,&v2);
long long ans=-100;
//先判断n/s1和n/s2是否够大，不至于超时
int cnt1=n/s1,cnt2=n/s2;
int cnt=min(cnt1,cnt2);
if(cnt<maxn) { //符合条件
if(cnt==cnt1) {
for(long long i=0;i<=cnt;++i) {
long long tmp=0;
tmp+=i*v1;
tmp+=(n-i*s1)/s2*v2;
ans=max(ans,tmp);
}
}
else if(cnt==cnt2) {
for(long long i=0;i<=cnt;++i) {
long long tmp=0;
tmp+=i*v2;
tmp+=(n-i*s2)/s1*v1;
ans=max(ans,tmp);
}
}
}
else {
int d=s1*s2/gcd(s1,s2);
cnt1=d/s1,cnt2=d/s2;
if(cnt1*v1>cnt2*v2) {
for(long long i=0;i<cnt2;++i) {
long long tmp=0;
tmp+=i*v2;
tmp+=(n-i*s2)/s1*v1;
ans=max(ans,tmp);
}
}
else {
for(long long i=0;i<cnt1;++i) {
long long tmp=0;
tmp+=i*v1;
tmp+=(n-i*s1)/s2*v2;
ans=max(ans,tmp);
}
}
}
printf("Case #%d: %lld\n",++kase,ans);
}
return 0;
}
如有不当之处出欢迎指出！