记录编号	294916	评测结果	AAAAAAAAAA
题目名称	[HNOI 1999] 快餐问题	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.071 s
提交时间	2016-08-12 21:04:15	内存使用	0.30 MiB

#include<cstdio>
#include<queue>
using namespace std;
int A,B,C,p1,p2,p3,n,t[20],na,nb,nc;
int dp[110][110];
//check[i][j]表示生产i个A，j个B，最多生产的C 
inline int min(int a,int b){
	return a<b?a:b;
}
inline int max(int a,int b){
	return a>b?a:b;
}
inline int min(int a,int b,int c){
	return min(min(a,b),c);
}

int main()
{
	freopen("meal.in","r",stdin);
	freopen("meal.out","w",stdout);
	scanf("%d%d%d",&A,&B,&C);
	scanf("%d%d%d",&p1,&p2,&p3);
	scanf("%d",&n);
	int sum=0;
	for (int i=1;i<=n;i++)
		scanf("%d",&t[i]),sum+=t[i];
	int Min=min(100/A,100/B,100/C);
	Min=min(Min,sum/(A*p1+B*p2+C*p3));
	na=A*Min;nb=B*Min;nc=C*Min;
	for (int i=0;i<=na;i++)
	for (int j=0;j<=nb;j++)
		dp[i][j]=-99999999;
	dp[0][0]=0;
	for (int i=1;i<=n;i++){
		for (int a=na;a>=0;a--)
		for (int b=nb;b>=0;b--)
		if (dp[a][b]>=0){
			for (int c=na-a;c>=0;c--)
			for (int d=nb-b;d>=0;d--)
			if (c*p1+d*p2<=t[i]){
				int e=(t[i]-c*p1-d*p2)/p3;
				dp[a+c][b+d]=max(dp[a+c][b+d],dp[a][b]+e);
			}
		}
		if (dp[na][nb]>=nc){
			printf("%d\n",Min);return 0;
		}
	}
	int ans=0;
	for (int i=0;i<=na;i++)
	for (int j=0;j<=nb;j++)
	if (dp[i][j]>=0)
		ans=max(ans,min(i/A,j/B,dp[i][j]/C));
	printf("%d\n",ans);
	return 0;
}