LSORTVN - LSORT

Tác giả: ladpro98

Ngôn ngữ: Pascal

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.

Download