记录编号	272311	评测结果	AAAAAAAAAA
题目名称	[HNOI 1999] 快餐问题	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.058 s
提交时间	2016-06-16 20:00:38	内存使用	1.00 MiB

#include<bits/stdc++.h>

//一条生产线时间t,产j汉堡k薯条,则生产(t*i-j*p1-k*p2)/p3饮料 
int f[15][110][110]={0};
//f[i][j][k]前i生产线生产j汉堡和k薯条,则最多生产的饮料数 
//另外要有第i生产线生产j汉堡k薯条,则生产饮料数 
int t[15]={0};
int a,b,c,p1,p2,p3,n,tot,ans=0,tc=0,maxn=0,maxa=0,maxb=0,maxc=0,pack=0;

inline int GetMax(const int& a,const int& b)
{
	return a>b?a:b;
}

inline int GetMin(int a, int b)
{
	return a<b?a:b;
}

bool Init()
{
	scanf("%d%d%d%d%d%d%d",&a,&b,&c,&p1,&p2,&p3,&n);
	tot=p1*a+p2*b+p3*c;
	int pack=0,tmp=0,sum=0;//最多生产pack个套餐 
	maxn=GetMin(100/a,GetMin(100/b,100/c));//最最最最多生产的套餐数 
	for (int i=1;i<=n;i++){
		scanf("%d",&t[i]);
		pack+=t[i]/tot;
		tc+=t[i]/tot;
		t[i]=t[i]%tot;
		sum+=t[i];
	}
	if(pack>=maxn)	return true;
	sum=sum/tot;//变成了能整个生产套餐数
	maxa=GetMin(sum*a,100);
	maxb=GetMin(sum*b,100);
	maxc=GetMin(sum*c,100);
	return false; 
}

inline bool Check(const int& i, const int& j, const int& k)
{
	int tmp=f[i][j][k];
	if(tmp>maxc){
		if((j<maxa&&(tmp-maxc)*p3>=p1) || (k<maxb&&(tmp-maxc)*p3)>=p2)
			return false;
	}
	return true;
} 

void Work()
{
	
	memset(f,-1,sizeof(f));
	f[0][0][0]=0;
	int tmp;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=maxa;j++){
			for(int k=0;k<=maxb;k++){
				//if(Check(i-1,j,k)){
				if (f[i-1][j][k] < maxc) {
					for(int j2=j;j2>=0;j2--){
						tmp=(j-j2)*p1;
						if(tmp>t[i])	break;
						for(int k2=k;k2>=0;k2--){
							tmp=(j-j2)*p1+(k-k2)*p2;
							if(tmp<=t[i]&&f[i-1][j2][k2]!=-1)
								f[i][j][k]=GetMax(f[i][j][k],f[i-1][j2][k2]+tmp/p3);
						}		
					}
				}
				else 	f[i][j][k]=f[i-1][j][k];	
			}	
		}	
	}
	for(int j=0;j<=maxa;j++)
		for(int k=0;k<=maxb;k++)
			ans=GetMax(GetMin(j/a,GetMin(k/b,f[n][j][k])),ans);
			
	printf("%d",ans+tc);		
}

int main(){
	freopen("meal.in","r",stdin);
	freopen("meal.out","w",stdout);
	int in=Init();
	if(in==true){
		printf("%d",maxn);
		return 0;
	}
	Work();	
	return 0;
}