比赛 20120710 评测结果 AAAAAAAAAA
题目名称 快餐问题 最终得分 100
用户昵称 ZhouHang 运行时间 0.226 s
代码语言 C++ 内存使用 0.86 MiB
提交时间 2012-07-10 10:58:03
显示代码纯文本
/**
*Prob	: meal
*Data	: 2012-7-10
*Sol	: dp+贪心
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define MaxN 15
#define MaxT 100

int n,a,b,c,p1,p2,p3;
int maxa,maxb,maxc;
int t[MaxN];
int f[MaxN][MaxT][MaxT];

int min(int x,int y)
{
	return x>y?y:x;
}
int max(int x,int y)
{
	return x>y?x:y;
}
int min(int x,int y,int z)
{
	int tmp = min(x,y);
	tmp = min(tmp,z);
	return tmp;
}

bool can(int i,int j,int k)
{
	if (f[i][j][k]==-1) return false;
	if (f[i][j][k]>maxc) {
		if ((j!=maxa)&&((f[i][j][k]-maxc)*p3>p1))
			return false;
		if ((k!=maxb)&&((f[i][j][k]-maxc)*p3>p2))
			return false;
	}
	return true;
}

int main()
{
	freopen("meal.in","r",stdin);
	freopen("meal.out","w",stdout);
	
	scanf("%d%d%d%d%d%d",&a,&b,&c,&p1,&p2,&p3);
	scanf("%d",&n);
	for (int i=1; i<=n; i++)
		scanf("%d",&t[i]);

	//答案上界
	int maxans = min(MaxT/a,MaxT/b,MaxT/c);
	//贪心-整套生产,骗分
	int ans2=0,tot = a*p1+b*p2+c*p3;
	for (int i=1; i<=n; i++)
		while ((t[i]>=3*tot)&&ans2<maxans) {
			t[i] -= tot;
			ans2 ++;
		}
	maxans -= ans2;
	
	//答案上界
	int sum = 0;
	for (int i=1; i<=n; i++)
		sum += t[i];
	maxans = min(maxans,sum/tot);
	maxa = maxans*a;
	maxb = maxans*b;
	maxc = maxans*c;
	
	memset(f,255,sizeof(f));
	f[0][0][0] = 0;
	//贪心处理答案上界
	for (int i=0; i<n; i++)
	 for (int j=0; j<=maxa; j++)
	  for (int k=0; k<=maxb; k++)
		if (can(i,j,k)) {
		 for (int x=0; x<=min(maxa-j,t[i+1]/p1); x++)
		  for (int y=0; y<=min(maxb-k,(t[i+1]-p1*x)/p2); y++)
		  {
			int z = (t[i+1]-p1*x-p2*y)/p3;
			f[i+1][j+x][k+y] = max(f[i+1][j+x][k+y],f[i][j][k]+z);
		  }
		}
	//答案
	int ans = 0;
	for (int j=0; j<=MaxT; j++)
	 for (int k=0; k<=MaxT; k++) {
		if (f[n][j][k]==-1) continue;
        int tmp = min(j/a,k/b,f[n][j][k]/c);
        ans = max(ans,tmp);
	 }
	
	printf("%d\n",ans+ans2);
	
	
	fclose(stdin); fclose(stdout);
	return 0;
}