Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

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.

Code mẫu của ladpro98

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.

Code mẫu của RR

//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.

Code mẫu của ll931110

{$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.

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int a[1010], vt[1010];
int n;
int F[1010][1010], L[1010][1010], R[1010][1010];

    int calc_left(int l, int r) {
        if (l == r)
            return vt[l];
        if (L[l][r] != -1)
            return L[l][r];
        return L[l][r] = calc_left(l, r - 1) - (vt[r] < vt[l] ? 1 : 0);
    }

    int calc_right(int l, int r) {
        if (l == r)
            return vt[l];
        if (R[l][r] != -1)
            return R[l][r];
        return R[l][r] = calc_right(l + 1, r) - (vt[l] < vt[r] ? 1 : 0);
    }

    int calc(int l, int r) {
        if (l > r)
            return 0;
        if (F[l][r] != -1)
            return F[l][r];
        return F[l][r] = min(calc(l + 1, r) + (r - l + 1) * calc_left(l, r), calc(l, r - 1) + (r - l + 1) * calc_right(l, r));
    }

int main() {
    scanf("%d", &n);
    for(int i=0;i<n;++i) scanf("%d", a + i);
    for(int i=0;i<n;++i) vt[a[i] - 1] = i + 1;  
    memset( F, -1, sizeof(F));
    memset( R, -1, sizeof(R));
    memset( L, -1, sizeof(L));
    int res = calc( 0, n-1);
    printf("%d\n", res);
    return 0;   
}