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=40010;
var n,z,i,j,k,u,x,lx:longint;
    f,d:array[1..maxn] of longint;
    g:array[0..1,1..210] of longint;

function min(u,v:longint):longint;
begin
     if u<v then min:=u else min:=v;
end;

begin
     read(n,i);
     z:=trunc(sqrt(n))+1;
     read(x); g[1,1]:=1; d[x]:=1;
     f[1]:=1; i:=1; u:=1; lx:=x;
     for k:=2 to n do
     begin
          i:=i+1;
          read(x);
          if x=lx then
          begin
               i:=i-1; continue;
          end;
          u:=1-u;
          {init}
          fillchar(g[u],sizeof(g[u]),0);
          g[u,1]:=i;
          for j:=1 to z do
          begin
               if g[1-u,j]>d[x] then g[u,j+1]:=g[1-u,j]
               else
                   if g[1-u,j]<d[x] then g[u,j]:=g[1-u,j];
               if g[1-u,j]=0 then break;
          end;
          d[x]:=i; lx:=x;
          {calc}
          f[i]:=f[i-1]+1;
          for j:=2 to z do
          begin
               f[i]:=min(f[i],f[g[u,j]]+sqr(j-1));
               if g[u,j]=0 then break;
          end;
     end;
     writeln(f[i]);
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>

const int N = 444444;
const int maxL = 2222;
const int oo = 123456789;
using namespace std;
int pos[maxL], f[N], a[N], last[N];
ii b[N];
int n, m, d;

int main()
{
    scanf("%d %d\n", &n, &m);
    int i, j, p, lim;
    for(i=1; i<=n; i++) {
        scanf("%d", &a[i]);
        b[i] = ii(a[i], i);
    }
    /*sort(b+1, b+1+n);
    for(i=1; i<=n; i++) {
        if (b[i].first != b[i-1].first) d++;
        a[b[i].second] = d;
    }*/
    for(i=1; i<maxL; i++) pos[i] = oo;
    f[1] = 1; pos[1] = 1; last[a[1]] = 1;
    lim = trunc(sqrt(n));
    for(i=2; i<=n; i++) {
        p = last[a[i]];
        for(j=lim; j>=1; j--) {
            //if (pos[j] == oo) break;
            //if (pos[j] <= p) break;
            if (pos[j+1] > p)
                pos[j + 1] = pos[j];
        }
        if (p != (i - 1)) pos[1] = i;
        last[a[i]] = i;
        f[i] = i;
        for(j=1; j<=lim; j++)
        if (pos[j] <= i)
            f[i] = min(f[i], f[pos[j] - 1] + j * j);
    }
    printf("%d", f[n]);
    return 0;
}

Code mẫu của RR

//Written by RR
{$R-,Q-}
{$Mode objfpc}
{$inline on}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       40111;
  MAXK          =       222;

var
  f1,f2         :       text;
  n,k           :       longint;
  a,f           :       array[0..MAXN] of longint;
  q             :       array[1..2,1..MAXK] of longint;
  now,next      :       array[1..MAXN] 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,i);
      for i:=1 to n do
        begin
          read(f1,a[i]);
        end;
    end;

procedure solve;
    var
      t,i,j,top,u,gh,now:longint;
    begin
      gh:=trunc(sqrt(n));
      now:=1;
      for i:=1 to n do
        begin
          //khoi tao q
          if i=1 then
            begin
              top:=1;
              q[now,1]:=1;
            end
          else if a[i]=a[i-1] then
            begin
              for j:=1 to top do
                q[now,j]:=q[3-now,j];
            end
          else if next[i]>=q[3-now,top] then
            begin
              u:=next[i]+1;
              t:=1; q[now,1]:=i;
              for j:=1 to top do
                if (t<gh) and (q[3-now,j]<>u) then
                  begin
                    inc(t);
                    q[now,t]:=q[3-now,j];
                  end;
              top:=t;
            end
          else
            begin
              t:=1; q[now,1]:=i;
              for j:=1 to top do
                if (t<gh) then
                  begin
                    inc(t);
                    q[now,t]:=q[3-now,j];
                  end;
              top:=t;
            end;

          //qhd
          f[i]:=high(longint);
          for j:=1 to top do
            f[i]:=min(f[i],f[q[now,j]-1]+j*j);
          now:=3-now;
        end;
      writeln(f2,f[n]);
    end;

procedure init;
    var
      i:longint;
    begin
      for i:=1 to n do
        begin
          next[i]:=now[a[i]];
          now[a[i]]:=i;
        end;
    end;

begin
  openF;
  inp;
  init;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
//#include <conio.h>
#include <iostream>

using namespace std;

int min(int a,int b) {return a<b?a:b; }

int main()
{
   // freopen("CTNCLN.in","r",stdin);
    int n,m,f[44444],a[44444],l[44444],t[222],can;
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
    for(can = 1;can*can<=n;can++); can--;
    memset(l,-1,m+1); memset(t,0,sizeof(t));
    t[0] = 1;
    int k,j;
    for(int i = 1;i<=n;i++)
    {
        k = l[a[i]];
        for(j = 0;j<=can && t[j]-1!=k;j++);
        for(j--;j>=0;j--)
            t[j+1] = t[j];
        t[0] = i+1;
        f[i] = i;
        for(j = 1;j<=can;j++)
            f[i] = min(f[i],f[t[j]-1]+j*j);
        l[a[i]]=i;
    }
    printf("%d",f[n]);
    //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program CTNCLN;
const
  input  = '';
  output = '';
  maxn = 40000;
  maxk = 201;
var
  F,a,prev: array[0..maxn] of integer;
  cur,next: array[1..maxk] of integer;
  n,m,k: integer;

procedure init;
var
  fi: text;
  i: integer;
begin
  assign(fi, input);
    reset(fi);

  readln(fi, n, m);
  for i := 1 to n do read(fi, a[i]);

  k := trunc(sqrt(n));
  if k > m then k := m;

  close(fi);
end;

procedure solve;
var
  u,i,j: integer;
begin
  fillchar(prev, sizeof(prev), 0);
  F[0] := 0;

  for i := 1 to n do
    begin
      F[i] := F[i - 1] + 1;  //First value
      u := prev[a[i]];
      prev[a[i]] := i;

      next[1] := i;
      for j := 1 to k do
        if cur[j] > 0 then
          begin
            if cur[j] > u then next[j + 1] := cur[j] else next[j] := cur[j];
          end;
      cur := next;

      for j := 1 to k do
        begin
          u := cur[j];
          if u = 0 then break;
          if F[i] > F[u - 1] + sqr(j)
            then F[i] := F[u - 1] + sqr(j);
        end;
    end;
end;

procedure printresult;
var
  fo: text;
begin
  assign(fo, output);
    rewrite(fo);
    writeln(fo, F[n]);
  close(fo);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của khuc_tuan

#include <iostream>
#include <set>
using namespace std;

int n, m;
int a[40040];
int F[40040];
int pos[40040];
set<int> se;

int main() {
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;++i) scanf("%d", &a[i]);
    memset( pos, -1, sizeof(pos));
    for(int i=1;i<=n;++i) {
        F[i] = i;
        if(pos[a[i]]!=-1) se.erase(pos[a[i]]);
        pos[a[i]] = i;
        se.insert(i);
        if(se.size() == 1) F[i] = 1;
        else {
            int id = 0;
            for(set<int> :: iterator p = se.end();;) {
                if(p==se.begin()) break;
                --p;
                ++id;
                if(id >= 2) F[i] <?= F[*p] + (id-1) * (id-1);
                if(id > 250) break;
            }
        }
    }
    cout << F[n] << endl;
    return 0;
}