比赛 20120710 评测结果 AAAWTAATTT
题目名称 快餐问题 最终得分 50
用户昵称 zhangchi 运行时间 5.584 s
代码语言 Pascal 内存使用 1.04 MiB
提交时间 2012-07-10 09:46:00
显示代码纯文本
var
  a,b,c,p1,p2,p3,n,i,j,k,l,temp,maxmeal:longint;
  g:array[1..10,0..100,0..100] of longint;
  dp:array[1..10,0..100,0..100] of longint;
  p:array[1..10,0..100,0..100] of boolean;
  time:array[1..10] of longint;
  function max(x,y:longint):longint;
  begin if x>y then max:=x else max:=y; end;
  function dfs(k,x,y:longint):longint;
  var
    i,j,temp:longint;
  begin
    if k<=0 then
      begin
        if (x<=0)and(y<=0) then exit(0);
        exit(-100);
      end;
    if p[k,x,y]=true then exit(dp[k,x,y]);
    temp:=-maxlongint div 2;
    for i:=0 to x do
      for j:=0 to y do
        temp:=max(temp,dfs(k-1,i,j)+g[k,x-i,y-j]);
    dp[k,x,y]:=temp;
    p[k,x,y]:=true;
    exit(dp[k,x,y]);
  end;
begin
  assign(input,'meal.in'); reset(input);
  assign(output,'meal.out'); rewrite(output);
  maxmeal:=maxlongint;
  readln(a,b,c);
  if 100 div a<maxmeal then maxmeal:=100 div a;
  if 100 div b<maxmeal then maxmeal:=100 div b;
  if 100 div c<maxmeal then maxmeal:=100 div c;
  readln(p1,p2,p3);
  readln(n);
  for i:=1 to n do
    read(time[i]);
  for i:=1 to n do
    for j:=0 to 100 do
      for k:=0 to 100 do
        begin
          g[i,j,k]:=(time[i]-j*p1-k*p2) div p3;
          if g[i,j,k]<0 then g[i,j,k]:=-maxlongint div 2;
        end;
  for i:=1 to maxmeal do
    begin
      temp:=dfs(n,i*a,i*b);
      if temp div i<c then
        begin
          writeln(i-1);
          close(input); close(output);
          halt;
        end;
    end;
  writeln(maxmeal);
  close(input); close(output);
end.