UVA-12325 宝箱 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

根据书上的方法来做，是比较简单的题目。关键在于知道等体积时的枚举法。不过数据大小可能很大，虽然输入可以用int处理，但是 体积*价值 后，需要long long才存的下。

#include
 
int n, s1, v1, s2, v2;
 
long long getCount(int num, int type) {
	long long sumV = 0, maxV = 0;
	for(int i = 0; i <= num; ++i) {
		if(type == 1) {
			if((n - i * s1) < 0) continue;
			sumV = (long long)i * v1 + ((long long)(n - i * s1) / s2) * v2;
		} else {
			if((n - i * s2) < 0) continue;
			sumV = (long long)i * v2 + ((long long)(n - i * s2) / s1) * v1;
		}
		// printf("%lld %lld\n", sumV, maxV);
		if(sumV > maxV) maxV = sumV;
	}
	return maxV;
}
 
 
long long getRes() {
	int a = n / s1;
	int b = n / s2;
	int type;
	if ((long long)s2 * v1 > (long long)s1 * v2) {
		type = 2; 
	} else if((long long)s2 * v1 < (long long)s1 * v2) {
		type = 1;
	} else {
		if(s1 > s2) {
			type = 1;
		} else {
			type = 2; 
		} 
	}
	int typeNum = type == 1 ? s2 : s1;
	// printf("%d %d %d %d\n", a, b, type, typeNum);
	if(a <= b && a <= typeNum) {
		return getCount(a, 1);
	}
	else if(b <= a && b <= typeNum) {
		return getCount(b, 2);
	}
	else if(typeNum <= a && typeNum <= b) {
		return getCount(typeNum, type);
	}
	return getCount(a, 1);
}
 
int main() {
	int t, ti = 0;
	scanf("%d", &t);
	while(ti++ != t) {
		scanf("%d %d %d %d %d", &n, &s1, &v1, &s2, &v2);
		// printf("%d\n", n);
		printf("Case #%d: %lld\n", ti, getRes());
	}
	return 0; 
}