KSPREE - Triple Shoot

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program KSPREE;
const
  input  = '';
  output = '';
  maxn = 20;
  maxk = (1 shl maxn) - 1;
  maxv = 1000000;
var
  a,k3: array[0..maxn] of integer;
  d: array[0..maxk] of integer;
  n: integer;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 0 to n - 1 do read(f, a[i]);

  close(f);
end;

procedure solve;
var
  i,j,k,cc,tmp: integer;
begin
  for i := 0 to 1 shl n - 1 do d[i] := maxv;
  d[1 shl n - 1] := 0;

  for i := 1 to n - 2 do
    k3[i] := (1 shl n) - 1 - (1 shl (i - 1)) - (1 shl i) - (1 shl (i + 1));

  k3[0] := (1 shl n) - 1 - (1 shl 0) - (1 shl 1) - (1 shl (n - 1));
  k3[n - 1] := (1 shl n) - 1 - (1 shl 0) - (1 shl (n - 1)) - (1 shl (n - 2));

  for i := 1 shl n - 1 downto 0 do if d[i] <> maxv then
    for j := 0 to n - 1 do
      begin
        tmp := i and k3[j];
        cc := 0;
        for k := 0 to n - 1 do
          if tmp and (1 shl k) = (1 shl k) then cc := cc + a[k];
        if d[tmp] > d[i] + cc then d[tmp] := d[i] + cc;
      end;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, d[0]);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Download