记录编号	254535	评测结果	AAAAAAAAAA
题目名称	[HNOI 1999] 快餐问题	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.776 s
提交时间	2016-04-25 14:50:02	内存使用	0.77 MiB

#include<cstdio>
#include<cctype>
#include<cstring>
int read(){
	int x;char ch;
	while(ch=getchar(),!isdigit(ch));
	x=ch-'0';
	while(ch=getchar(),isdigit(ch))x=x*10+ch-'0';
	return x;
}
int f[12][102][102];
int t[12];
int min(int a,int b){
	return a<b?a:b;
}
int max(int a,int b){
	return a>b?a:b;
}
int sum,needa,needb,needc,costa,costb,costc,n,maxa,maxb,maxc;
bool enough(int lsx,int a,int b){
	int tmp=f[lsx][a][b],rest=sum-tmp*costc-a*costa-b*costb>costa;
	if(tmp>maxc){
		if((a<maxa&&rest>costa)||(b<maxb&&rest>costb))return true;
	}
	return false;
}
int main(){
	freopen("meal.in","r",stdin);
	freopen("meal.out","w",stdout);
	sum=0;
	needa=read();needb=read();needc=read();
	costa=read();costb=read();costc=read();
	n=read();
	memset(f,-1,sizeof(f));
	for(int i=1;i<=n;++i){
		t[i]=read();
		sum+=t[i];
	}
	int tot=sum/(costa*needa+costb*needb+costc*needc);
	maxa=min(tot*needa,100);
	maxb=min(tot*needb,100);
	maxc=min(tot*needc,100);
	f[0][0][0]=0;
	for(int lsx=1;lsx<=n;++lsx){
		for(int proa=0;proa<=maxa;++proa){
			for(int prob=0;prob<=maxb;++prob){
				f[lsx][proa][prob]=f[lsx-1][proa][prob];
				if(enough(lsx,proa,prob))continue;
				int tmp;
				for(int guessa=proa;guessa>=0;guessa--){
					if(f[lsx][proa][prob]>=maxc)continue;
					for(int guessb=prob;guessb>=0;guessb--){
						tmp=t[lsx]-guessa*costa-guessb*costb;
						if(tmp<0)continue;
						if(f[lsx-1][proa-guessa][prob-guessb]!=-1)
		f[lsx][proa][prob]=max(f[lsx][proa][prob],f[lsx-1][proa-guessa][prob-guessb]+tmp/costc);
					}
				}
				
			}
		}
	}
	
	int ans=0;
	for(int proa=0;proa<=maxa;++proa){
		for(int prob=0;prob<=maxb;++prob){
			ans=max(ans,min(f[n][proa][prob],min(proa/needa,prob/needb)));
		}
	}
	printf("%d",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}
/*
1 3 2 
3 1 2 
4
15 61 62 64 
*/