CHNREST - Chinese restaurant

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxc=59048;
      maxs=2000000000;
type ar=array[0..maxc] of longint;
var n,m,re:longint;
    p,p3:array[0..15] of longint;
    a:array[0..29] of longint;
    d:array[0..9,0..29] of byte;
    b:array[0..9] of longint;
    f,g:ar;

procedure rf;
var i,j,t:longint;
begin
     assign(input,fi);
     reset(input);
     readln(m,n);
     for i:=0 to m-1 do read(a[i]);
     readln;
     fillchar(d,sizeof(d),0);
     for i:=0 to n-1 do
     begin
          while not seekeoln do
          begin
               read(t);
               d[i,t-1]:=1;
          end;
          readln;
     end;
     close(input);
end;

procedure init;
var i:longint;
begin
     p[0]:=1; p3[0]:=1;
     for i:=1 to 15 do
     begin
          p[i]:=p[i-1]*2;
          p3[i]:=p3[i-1]*3;
     end;
end;

procedure work(var f:ar;l,s:longint);
var i,j,t,max,num,pri,k:longint; kt:boolean;
begin
     f[0]:=0;
     for i:=1 to p3[n]-1 do f[i]:=maxs;
     max:=p[l]-1;
     dec(l);
     for i:=1 to max do
     begin
          t:=i; pri:=0; num:=0;
          fillchar(b,sizeof(b),0);
          for j:=0 to l do
          begin
               if t and 1 = 1 then
               begin
                    for k:=0 to n-1 do
                        if d[k,j+s]=1 then b[k]:=b[k]+1;
                    pri:=pri+a[j+s];
               end;
               t:=t shr 1;
               if t=0 then break;
          end;
          kt:=true;
          for j:=0 to n-1 do
              if b[j]>2 then
              begin
                   kt:=false;
                   break;
              end
              else num:=num+b[j]*p3[j];
          if (f[num]>pri) and kt then f[num]:=pri;
     end;
end;

procedure pr;
var i,max:longint;
begin
     init;
     work(f,m div 2,0);
     work(g,m-m div 2,m div 2);
     max:=p3[n]-1;
     re:=maxs;
     for i:=0 to max do
         if (f[i]<maxs) and (g[max-i]<maxs) and (f[i]+g[max-i]<re) then
            re:=f[i]+g[max-i];
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     if re<maxs then write(re)
     else write(-1);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download