比赛 |
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;
}