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.

Download