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.

Download