stamps.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:stamps
}

program stamps;
const
  maxn=50;
  maxvalue=2000000;
var
  fin,fout:text;
  q:array[0..maxvalue]of longint;
  need:array[0..maxvalue+1]of byte;
  value:array[1..maxn]of word;
  k,n,i,f,r:longint;
begin
  assign(fin,'stamps.in');
  reset(fin);
  read(fin,k,n);
  for i:=1 to n do
    read(fin,value[i]);
  close(fin);

  fillchar(need,sizeof(need),255);need[0]:=0;
  f:=-1;r:=0;q[0]:=0;
  repeat
    inc(f);
    if need[q[f]]=k then break;
    for i:=1 to n do
      if need[q[f]]+1<need[q[f]+value[i]] then begin
        inc(r);q[r]:=q[f]+value[i];need[q[f]+value[i]]:=need[q[f]]+1;
      end;
  until false;

  assign(fout,'stamps.out');
  rewrite(fout);
  i:=0;repeat inc(i);until need[i]=255;
  writeln(fout,i-1);
  close(fout);
end.