比赛 20120710 评测结果 AAAAAWTTTT
题目名称 快餐问题 最终得分 50
用户昵称 CC 运行时间 4.841 s
代码语言 C++ 内存使用 5.81 MiB
提交时间 2012-07-10 11:41:09
显示代码纯文本
#include <cstdio>
#include <algorithm>
#define INF 1000000000
int A,B,C,a,b,c,n,K;
int f[105][105][105];
bool ok[105][105][105],out;
int main() {
	freopen("meal.in","r",stdin);
	freopen("meal.out","w",stdout);
	scanf("%d%d%d", &A, &B, &C);
	scanf("%d%d%d", &a, &b, &c);
	scanf("%d", &n);
	ok[0][0][0] = 1;
	for (int i = 1;i <= n;i++) {
		scanf("%d", &K);
		out = 0;
		for (int p = 0;p <= 100;p++) {
			if (!ok[i - 1][p][0]) break;
			for (int q = 0;q <= 100;q++) {
				if (!ok[i - 1][p][q]) break;
				for (int u = 0;u <= 100;u++) {
					if (u * a > K) break;
					for (int v = 0;v <= 100;v++) {
						if (u * a + v * b > K) break;
						ok[i][p + u][q + v] = 1;
						f[i][p + u][q + v] = f[i - 1][p][q] + (K - u * a - v * b) / c;
					}
				}
			}
		}
	}
	int tmp,ans = 0;
	for (int i = 0;i <= 100;i++)
		for (int j = 0;j <= 100;j++) 
			if (ok[n][i][j]) {
				int k = f[n][i][j];
				tmp = INF;
				tmp = std::min(tmp,i / A);
				tmp = std::min(tmp,j / B);
				tmp = std::min(tmp,k / C);
				ans = ans < tmp ? tmp : ans;
			}
	printf("%d\n", ans);
	return 0;
}