LSORTVN - LSORT
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=1001;
var n,test,it:longint;
b:array[1..maxn] of longint;
a,f:array[0..maxn,0..maxn] of longint;
procedure rf;
var i,j:longint;
begin
read(n);
for i:=1 to n do
begin
read(j); b[j]:=i;
end;
for i:=1 to n do
begin
a[i,0]:=0; a[i,i]:=0;
for j:=1 to n do
if i<>j then
begin
if b[j]<b[i] then a[i,j]:=a[i,j-1]+1
else a[i,j]:=a[i,j-1];
end;
end;
end;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
function calc(k,l,r:longint):longint;
begin
calc:=a[k,r]-a[k,l-1];
end;
procedure pr;
var i,j,l:longint;
begin
for i:=1 to n do f[i,i]:=b[i];
for l:=2 to n do
for i:=1 to n-l+1 do
begin
j:=i+l-1;
f[i,j]:=min(f[i,j-1]+l*(b[j]-calc(j,i,j-1)),f[i+1,j]+l*(b[i]-calc(i,i+1,j)));
end;
end;
procedure wf;
begin
writeln(f[1,n]);
end;
begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
rf;
pr;
wf;
close(input); close(output);
end.