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.

Download