站外题

题目描述

某快餐店推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。快餐店从著名的麦当捞公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。

输入格式

第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1，p2，p3分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0≤N≤10)，第四行为N个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。

样例输入 2 2 2 1 2 2 2 6 6 样例输出 1

代码

#include<bits/stdc++.h>
using namespace std;
int n, pa, pb, pc, A, B, C, t[15], dp[15][105][105], mpc_a, mpc_b, mpc_c, mpc;
int main()
{
	scanf ( "%d %d %d\n%d %d %d\n%d", &A, &B, &C, &pa, &pb, &pc, &n );
	mpc = min ( ceil ( 100.0 / A ), min ( ceil ( 100.0 / B ), ceil ( 100.0 / C ) ) );
	mpc_a = mpc * A;
	mpc_b = mpc * B;
	mpc_c = mpc * C;
	for ( int i = 1; i <= n; i++ ) {
		scanf ( "%d", &t[i] );
	}
	for ( int i = 1; i <= n; i++ ) {
		for ( int tot_a = 0; tot_a <= mpc_a; tot_a++ ) {
			for ( int tot_b = 0; tot_b <= mpc_b; tot_b++ ) {
				for ( int new_a = 0; new_a <= tot_a && new_a * pa <= t[i]; new_a++ ) {
					for ( int new_b = 0; new_b <= tot_b && new_b * pb + new_a * pa <= t[i]; new_b++ ) {
						dp[i][tot_a][tot_b] = max ( dp[i][tot_a][tot_b], dp[i - 1][tot_a - new_a][tot_b - new_b] + ( int ) ( ( t[i] - pa * new_a - pb * new_b ) * 1.0 / pc ) );
					}
				}
			}
		}
	}
	int ans = -1;
	for ( int tot_a = 0; tot_a <= mpc_a; tot_a++ ) {
		for ( int tot_b = 0; tot_b <= mpc_b; tot_b++ ) {
			ans = max ( ans, ( int ) min ( dp[n][tot_a][tot_b] * 1.0 / C, min ( tot_a * 1.0 / A, tot_b * 1.0 / B ) ) );
		}
	}
	printf ( "%d", ans );
	return 0;
}