HUGEKNAP - Cái túi ( Hard version )

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=10000;
  MAXM=1000;
type
  list=^node;
  node=record
         u,v,val:longint;
         next:list;
       end;
  arr=array[1..MAXN,1..MAXM] of longint;
  arr2=array[0..MAXN] of longint;
  arr3=array[0..MAXM] of longint;
var
  f1,f2:text;
  luuu,luuv,kq,m,n,test:longint;
  v,w:^arr2;
  ln,last:arr3;
  trace:^arr;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i:longint;
begin
  read(f1,n,m);
  for i:=1 to n do read(f1,w^[i]);
  for i:=1 to n do read(f1,v^[i]);
end;
procedure solve;
var
  i,x,temp:longint;
begin
  fillchar(ln,sizeof(ln),0);
  fillchar(last,sizeof(last),0);
  for i:=1 to n do
    for x:=m downto w^[i] do
    if (x=w^[i]) or (last[x-w^[i]]<>0) then
      begin
        temp:=ln[x-w^[i]]+v^[i];
        if temp>ln[x] then
          begin
            ln[x]:=temp;
            last[x]:=i;
            trace^[i,x]:=last[x-w^[i]];
          end;
      end;
  kq:=0;
  for i:=1 to m do
    if ln[i]>kq then
      begin
        kq:=ln[i];
        luuu:=last[i];
        luuv:=i;
      end;
end;
procedure ans; inline;
var
  u,v,k,count:longint;
begin
  write(f2,kq,' ');
  u:=luuu; v:=luuv;
  count:=0;
  while v>0 do
    begin
      k:=trace^[u,v];
      inc(count);
      v-=w^[u]; u:=k;
    end;
  writeln(f2,count);
  u:=luuu; v:=luuv;
  while v>0 do
    begin
      k:=trace^[u,v];
      write(f2,u,' ');
      v-=w^[u];
      u:=k;
    end;
  writeln(f2);
end;
begin
  openF;
  read(f1,test);
  getMem(trace,MAXM*MAXN*sizeof(longint));
  getMem(v,sizeof(arr2));
  getMem(w,sizeof(arr2));
  for test:=1 to test do
    begin
      inp;
      solve;
      ans;
    end;
  freeMem(trace,MAXN*MAXM*sizeof(longint));
  freeMem(v,sizeof(arr2));
  freeMem(w,sizeof(arr2));
  closeF;
end.

Download