LSORTVN - LSORT
Tác giả: ladpro98
Ngôn ngữ: Pascal
program LSORTVN;
uses math;
const maxn=1111;
fi='';
var pos,a:array[0..maxn] of longint;
f,p:array[0..maxn,0..maxn] of longint;
n:longint;
procedure input;
var inp:text;
i:longint;
begin
assign(inp,fi);reset(inp);
readln(inp,n);
for i:=1 to n do begin
read(inp,a[i]);
pos[a[i]]:=i;
end;
close(inp);
end;
procedure init;
var i,j:longint;
begin
for i:=1 to n do
for j:=1 to n do
if a[i]<=j then p[i,j]:=p[i-1,j]+1
else p[i,j]:=p[i-1,j];
end;
procedure dp;
var i,j,len,costI,costJ:longint;
begin
for len:=0 to n-1 do
for i:=1 to n-len do begin
j:=i+len;
costI:=(len+1)*(pos[i]-p[pos[i]-1,j]+p[pos[i]-1,i-1]);
costJ:=(len+1)*(pos[j]-p[pos[j]-1,j]+p[pos[j]-1,i-1]);
f[i,j]:=min(f[i+1,j]+costI,f[i,j-1]+costJ);
end;
end;
begin
input;
init;
dp;
write(f[1,n]);
end.