VMSWAP - Đổi chỗ

Tác giả: ladpro98

Ngôn ngữ: Pascal

program VMSWAP;
uses    math;
const   fi='';
        maxn=1111;
var     f,g:array[1..maxn,0..maxn] of longint;
        a:array[1..maxn] of longint;
        n,i,j,res,s,t:longint;
        inp:text;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        for i:=1 to n do read(inp,a[i]);
        for i:=1 to n do
        for j:=n downto 1 do
        if i>a[j] then f[i,j]:=f[i,j+1]+1
        else f[i,j]:=f[i,j+1];
        for i:=1 to n do
        for j:=1 to n do
        if a[j]>i then g[i,j]:=g[i,j-1]+1
        else g[i,j]:=g[i,j-1];
        for i:=1 to n do inc(s,f[a[i],i]);
        res:=s;
        for i:=1 to n-1 do
        for j:=i+1 to n do begin
                t:=s+f[a[i],j+1]+f[a[j],i+1]-f[a[i],i]-f[a[j],j];
                t:=t+g[a[i],j]-g[a[i],i]-g[a[j],j]+g[a[j],i];
                res:=min(res,t);
        end;
        write(res);
end.

Download