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.

Download