shopping.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:shopping
}

program shopping;
const
  maxoffers=99;
  maxobj=5;
  maxedges=maxoffers+maxobj;
  maxnode=7775;
  e:array[1..6]of word=(1,6,36,216,1296,7776);
type
  offertype=record
    kinds:byte;
    id:array[1..5]of word;
    count:array[1..5]of byte;
    price:word;
  end;
var
  fin,fout:text;
  offer:array[1..maxoffers]of offertype;
  wantid,wantcount:array[1..maxobj]of word;
  cost:array[0..maxnode]of longint;
  obj,price:array[1..maxedges]of word;{edges}
  s,b,i,j,k,target:word;
  t:longint;
function merge(x,y:word):word;
  var
    m,i,t:word;
  begin
    m:=0;
    for i:=1 to b do begin
      t:=x mod e[i+1] div e[i]+y mod e[i+1] div e[i];
      if t>wantcount[i] then t:=wantcount[i];
      inc(m,e[i]*t);
    end;
    merge:=m;
  end;
begin
  assign(fin,'shopping.in');
  reset(fin);
  read(fin,s);
  for i:=1 to s do begin
    read(fin,offer[i].kinds);
    for j:=1 to offer[i].kinds do
      read(fin,offer[i].id[j],offer[i].count[j]);
    read(fin,offer[i].price);
  end;
  read(fin,b);
  for i:=1 to b do begin
    read(fin,wantid[i],wantcount[i]);
    obj[i]:=e[i];read(fin,price[i]);
  end;
  close(fin);

  for i:=1 to s do begin
    obj[i+b]:=0;
    for j:=1 to offer[i].kinds do
      for k:=1 to b do
        if offer[i].id[j]=wantid[k] then begin
          inc(obj[i+b],e[k]*offer[i].count[j]);
          break;
        end;
    price[i+b]:=offer[i].price;
  end;
  inc(s,b);

  target:=0;for i:=1 to b do inc(target,e[i]*wantcount[i]);
  cost[0]:=0;
  for i:=1 to target do
    cost[i]:=maxlongint;
  for i:=0 to target-1 do
    if cost[i]<maxlongint then
      for j:=1 to s do begin
        k:=merge(i,obj[j]);
        t:=cost[i]+price[j];
        if t<cost[k] then cost[k]:=t;
      end;

  assign(fout,'shopping.out');
  rewrite(fout);
  writeln(fout,cost[target]);
  close(fout);
end.