CHNREST - Chinese restaurant
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
program CHNREST;
const
input = '';
output = '';
maxm = 30;
maxn = 10;
maxk = 100000;
var
m,n: integer;
fav: array[1..maxn,1..maxm] of boolean;
s: array[0..maxm] of integer;
cost: array[1..maxm] of int64;
nfav,p: array[1..maxn] of integer;
d,l,r: array[0..maxk] of int64;
nover,pos: integer;
sum: int64;
procedure init;
var
f: text;
i,x: integer;
begin
assign(f, input);
reset(f);
readln(f, m, n);
for i := 1 to m do read(f, cost[i]);
fillchar(fav, sizeof(fav), false);
readln(f);
for i := 1 to n do
begin
while not Seekeoln(f) do
begin
read(f, x);
fav[i,x] := true;
end;
readln(f);
end;
close(f);
end;
procedure load(j: integer);
var
i,k: integer;
begin
sum := sum + cost[j];
for i := 1 to n do if fav[i,j] then
begin
k := nfav[i];
inc(nfav[i]);
if (k <= 2) and (nfav[i] > 2) then inc(nover);
pos := pos + p[i];
end;
end;
procedure unload(j: integer);
var
i,k: integer;
begin
sum := sum - cost[j];
for i := 1 to n do if fav[i,j] then
begin
k := nfav[i];
dec(nfav[i]);
if (k > 2) and (nfav[i] <= 2) then dec(nover);
pos := pos - p[i];
end;
end;
procedure attempt(i,sup: integer);
var
j: integer;
begin
for j := s[i - 1] + 1 to sup do
begin
load(j);
s[i] := j;
if nover = 0 then
begin
if (d[pos] > sum) or (d[pos] = -1) then d[pos] := sum;
attempt(i + 1,sup);
end;
unload(j);
end;
end;
procedure reset;
var
i: integer;
begin
sum := 0;
pos := 0;
for i := 1 to p[n + 1] - 1 do d[i] := -1;
d[0] := 0;
end;
procedure solve;
var
i,j: integer;
begin
p[1] := 1;
for i := 2 to n + 1 do p[i] := p[i - 1] * 3;
reset;
s[0] := 0;
attempt(1,m div 2);
l := d;
reset;
s[0] := m div 2;
attempt(1,m);
r := d;
sum := -1;
for i := 0 to p[n + 1] - 1 do
begin
j := p[n + 1] - 1 - i;
if (l[i] <> -1) and (r[j] <> -1) then
if (sum > l[i] + r[j]) or (sum = -1) then sum := l[i] + r[j];
end;
end;
procedure printresult;
var
f: text;
begin
assign(f, output);
rewrite(f);
writeln(f, sum);
close(f);
end;
begin
init;
solve;
printresult;
end.