holstein.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:holstein
}

program holstein;
const
  maxv=25;
  maxg=15;
var
  fin,fout:text;
  need,have:array[1..maxv]of integer;
  feed:array[1..maxg,1..maxv]of integer;
  s,ans:array[1..maxg]of boolean;
  v,g,i,j,c,ansc:byte;
function enough:boolean;
  var
    i:byte;
  begin
    enough:=false;
    for i:=1 to v do
      if have[i]<need[i] then exit;
    enough:=true;
  end;
procedure update;
  begin
    if c<ansc then begin
      ansc:=c;
      ans:=s;
    end;
  end;
procedure search(l:byte);
  var
    i:byte;
  begin
    s[l]:=true;inc(c);
    for i:=1 to v do
      inc(have[i],feed[l,i]);
    if enough then update else if l<g then search(l+1);
    s[l]:=false;dec(c);
    for i:=1 to v do
      dec(have[i],feed[l,i]);
    if l<g then search(l+1);
  end;
begin
  assign(fin,'holstein.in');
  reset(fin);
  readln(fin,v);
  for i:=1 to v do
    read(fin,need[i]);
  readln(fin,g);
  for i:=1 to g do
    for j:=1 to v do
      read(fin,feed[i,j]);
  close(fin);

  ansc:=g;
  fillchar(ans,sizeof(ans),1);
  fillchar(have,sizeof(have),0);
  c:=0;
  search(1);

  assign(fout,'holstein.out');
  rewrite(fout);
  write(fout,ansc);
  for i:=1 to g do
    if ans[i] then write(fout,' ',i);
  writeln(fout);
  close(fout);
end.