LSORTVN - LSORT
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program LSORTVN;
Const
input = '';
output = '';
maxn = 1000;
Var
n: integer;
a,pos: array[0..maxn] of integer;
F,le,gr: array[0..maxn,0..maxn] of integer;
Procedure init;
Var
fi: text;
i: integer;
Begin
Assign(fi, input);
Reset(fi);
Readln(fi, n);
For i:= 1 to n do
Begin
read(fi, a[i]);
pos[a[i]]:= i;
End;
Close(fi);
End;
Procedure gens;
Var
i,j: integer;
Begin
Fillchar(gr, sizeof(gr), 0);
Fillchar(le, sizeof(le), 0);
For i:= 1 to n do
Begin
For j:= 1 to a[i] - 1 do inc(gr[j,i]);
For j:= a[i] + 1 to n do inc(le[j,i]);
End;
For i:= 2 to n do
For j:= 1 to n do
Begin
gr[j,i]:= gr[j,i] + gr[j,i - 1];
le[j,i]:= le[j,i] + le[j,i - 1];
End;
End;
Procedure solve;
Var
i,j,n1,n2,len: integer;
Begin
For i:= 1 to n do F[i,i]:= pos[i];
For len:= 1 to n - 1 do
For i:= 1 to n - len do
Begin
j:= i + len;
n1:= F[i + 1,j] + (len + 1) * (pos[i] - (gr[i,pos[i] - 1] - gr[j,pos[i] - 1]));
n2:= F[i,j - 1] + (len + 1) * (pos[j] - (le[j,pos[j] - 1] - le[i,pos[j] - 1]));
If n1 > n2 then F[i,j]:= n2 else F[i,j]:= n1;
End;
End;
Procedure printresult;
Var
fo: text;
Begin
Assign(fo, output);
Rewrite(fo);
Writeln(fo, F[1,n]);
Close(fo);
End;
Begin
init;
gens;
solve;
printresult;
End.