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.