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.