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 maxn=20000;
var n,re,m,s,u:longint;
    a:array[1..maxn] of longint;
    f,dem:array[1..maxn,1..10] of longint;
    sum:array[1..10,0..1023] of longint;
    b,d:array[1..10] of longint;

procedure rf;
var i,x,y,j:longint;
begin
     read(n,m);
     read(a[1]); inc(d[a[1]]);
     for i:=2 to n do
     begin
          read(a[i]);
          dem[i]:=dem[i-1];
          dem[i,a[i-1]]:=dem[i,a[i-1]]+1;
          inc(d[a[i]]);
     end;
     for i:=1 to n do
         for j:=1 to m do
             f[a[i],j]:=f[a[i],j]+dem[i,j];
     for i:=1 to m do f[i,i]:=0;
     for i:=1 to m do
         for x:=1 to 1 shl m-1 do
             for j:=0 to m-1 do
                 if (x shr j) and 1=1 then sum[i,x]:=sum[i,x]+f[i,j+1];
end;

procedure att(i:longint);
var j:longint;
begin
     if i>m then
     begin
          if s<re then re:=s; exit;
     end;
     for j:=1 to m do
     if b[j]=0 then
     begin
          b[j]:=1;
          s:=s+sum[j,u];
          u:=u+1 shl (j-1);
          if s<re then att(i+1);
          b[j]:=0;
          u:=u-1 shl (j-1);
          s:=s-sum[j,u];
     end;
end;

procedure pr;
var i,j,min,x:longint;
begin
     re:=n*(n-1) div 2; s:=0; u:=0;
     att(1);
end;

procedure wf;
begin
     writeln(re);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 20002;
const int K = 11;
using namespace std;

int a[N], F[K][K], cnt[K];
int dp[1 << K];
int n, k;

void minimize(int &a, int b) {a = a > b ? b : a;}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    FOR(i, 0, n) {
        cin >> a[i]; a[i]--;
        FOR(j, 0, k)
        if (j != a[i]) F[a[i]][j] += cnt[j];
        cnt[a[i]]++;
    }
    FOR(i, 1, 1 << k) dp[i] = INT_MAX;
    FOR(i, 0, 1 << k) {
        FOR(j, 0, k) {
            if ((i & (1 << j)) == 0) {
                int cost = 0;
                FOR(t, 0, k) if (i & (1 << t)) cost += F[t][j];
                minimize(dp[i | (1 << j)], dp[i] + cost);
            }
        }
    }
    cout << dp[(1 << k) - 1];
    return 0;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       20111;
  MAXK          =       10;
  oo            =       1000111000;
var
  f1,f2         :       text;
  n,k           :       longint;
  d             :       array[1..MAXK,1..MAXK] of longint;
  f             :       array[0..1 shl MAXK] of longint;
  a,right       :       array[1..MAXN] of longint;
  dd            :       array[1..MAXK] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    var
      i:longint;
    begin
      read(f1,n,k);
      for i:=1 to n do
        read(f1,a[i]);
    end;
function get(color:longint):longint; inline;
    var
      i,kq:longint;
    begin
      kq:=0;
      for i:=1 to k do
        if dd[i]=0 then kq+=d[i,color];
      exit(kq);
    end;
procedure solve;
    var
      i,ii,color,j,jj:longint;
    begin
      for color:=1 to k do
        begin
          for i:=n downto 1 do
            if a[i]=color then right[i]:=right[i+1]+1
            else right[i]:=right[i+1];
          for i:=1 to n do
            if a[i]<>color then
              d[a[i],color]+=right[i];
        end;
      for i:=1 to 1<<k-1 do f[i]:=oo;
      for i:=0 to 1<<k-2 do
        begin
          fillchar(dd,sizeof(dd),0);
          for j:=1 to k do
            if (i>>(j-1)) and 1=1 then dd[j]:=1;
          for color:=1 to k do
            if (i>>(color-1)) and 1=0 then
              begin
                ii:=i+1<<(color-1);
                f[ii]:=min(f[ii],f[i]+get(color));
              end;
        end;
      writeln(f2,f[1<<k-1]);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define mod 790972
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
#define maxn 505
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, -1, 0, +1};

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

int num[11] = {0}, f[11][11] = {0}, x;
int n, k;
long long d[1 << 10] = {0};

int main(){
   // OPEN();
    scanf("%d %d", &n, &k);

    rep(i, n){
        scanf("%d", &x);
        x --;
        rep(j, k) f[x][j] += num[j];
        num[x]++;
    }

    FOR(i, 1, (1 << k) - 1){
        d[i] = 1ll << 60;
        rep(j, 10) if((i >> j) & 1){
            long long tang = 0;
            rep(k, 10) if(!((i >> k) & 1)) tang += f[j][k];
            d[i] = min(d[i], tang + d[i - (1 << j)]); 
        } 
    }

    cout << d[(1 << k) - 1];
}