【题解】UVa 12325【Zombie’s Treasure Chest 】

分析

这里可以先枚举宝物$1$的个数,然后尽量多拿宝物$2$,这样是当$N\div S_1$比较小时的做法,否则当$N\div S_2$比较小时,枚举宝物$2$的个数,否则说明$S_1$和$S_2$都比较小,这样就枚举$\max(S_2\times V_1,S_1\times V_2)$。

代码

#include<cstdio>
#include<algorithm>
typedef long long int64;
using std::swap;using std::max;
int main(){
    int T,id = 0;scanf("%d",&T);
    while(T--){
        int n,s1,v1,s2,v2;scanf("%d %d %d %d %d",&n,&s1,&v1,&s2,&v2);
        if(s1 > s2) swap(s1,s2),swap(v1,v2);
        int64 ans = 0;
        if(n / s2 >= 65536){
            for(int64 i = 0;i <= s1;i++) ans = max(ans,v2 * i + (n - s2 * i) / s1 * v1);
            for(int64 i = 0;i <= s2;i++) ans = max(ans,v1 * i + (n - s1 * i) / s2 * v2);
        }else{
            for(int64 i = 0;s2 * i <= n;i++) ans = max(ans,v2 * i + (n - s2 * i) / s1 * v1);
        }
        printf("Case #%d: %lld\n",++id,ans);
    }

    return 0;
}