LSORTVN - LSORT
Tác giả: RR
Ngôn ngữ: Pascal
//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
FINP='';
FOUT='';
MAXN=1111;
var
f1,f2 : text;
n,test : longint;
a,pos : array[1..MAXN] of longint;
c1,c2,d : array[1..MAXN,1..MAXN] of longint;
procedure inp;
var
i:longint;
begin
read(f1,n);
for i:=1 to n do
begin
read(f1,a[i]);
pos[a[i]]:=i;
end;
end;
procedure solve;
var
i,j,k:longint;
begin
//Calculate c1
for i:=1 to n do c1[i,i]:=0;
for k:=1 to n-1 do
for i:=1 to n-k do
begin
j:=i+k;
c1[i,j]:=c1[i,j-1];
if pos[j]<pos[i] then
c1[i,j]+=1;
end;
//Calculate c2
for i:=1 to n do c2[i,i]:=0;
for k:=1 to n-1 do
for i:=1 to n-k do
begin
j:=i+k;
c2[i,j]:=c2[i+1,j];
if pos[i]<pos[j] then c2[i,j]+=1;
end;
//Calculate d
for i:=1 to n do d[i,i]:=pos[i];
for k:=1 to n-1 do
for i:=1 to n-k do
begin
j:=i+k;
d[i,j]:=min(d[i,j-1]+(k+1)*(pos[j]-c2[i,j]),
d[i+1,j]+(k+1)*(pos[i]-c1[i,j]));
end;
writeln(f2,d[1,n]);
end;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
// read(f1,test);
test:=1;
for test:=1 to test do
begin
inp;
solve;
end;
close(f1); close(f2);
end.