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=202;
var n,i,j,k,l,t,x,y:longint;
    f:array[0..maxn,0..maxn,0..maxn] of longint;
    g:array[0..maxn,0..maxn] of longint;
    sl:array[0..9] of longint;
    a:array[0..9,1..200] of longint;
    s:string;
    kt:boolean;

function max(x,y:longint):longint;
begin
     if x>y then max:=x else max:=y;
end;

procedure init;
var i,x:longint;
begin
     fillchar(sl,sizeof(sl),0);
     for i:=1 to n do
     begin
          x:=ord(s[i])-48;
          inc(sl[x]);
          a[x,sl[x]]:=i;
     end;
end;

function findpos(x,i:longint):longint;
var j:longint;
begin
     for j:=1 to sl[x] do
         if a[x,j]>=i then
         begin
              findpos:=j; exit;
         end;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     readln(n);
     readln(s);
     init;
     for i:=1 to n do g[i,i]:=1;
     for l:=2 to n do
       for i:=1 to n-l+1 do
       begin
          j:=i+l-1;
          x:=ord(s[i])-48;
          y:=findpos(x,i);
          for k:=1 to l do
          begin
              kt:=false;
              for t:=y+k-1 to sl[x] do
                if a[x,t]>j then break
                else
                begin
                     kt:=true;
                     if a[x,t]=j then f[i,j,k]:=max(f[i,j,k],f[i,j-1,k-1])
                     else f[i,j,k]:=max(f[i,j,k],f[i,a[x,t],k]+g[a[x,t]+1,j]);
                end;
              if kt then g[i,j]:=max(g[i,j],f[i,j,k]+k*k);
          end;
       end;
     writeln(g[1,n]);
     close(input); close(output);
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 202;
using namespace std;
int a[N], v[N];
char s[N];
int F[N][N][N];
bool was[N][N][N];
int n, m;

int DP(int l, int r, int k) {
    if (was[l][r][k]) return F[l][r][k];
    was[l][r][k] = true;
    if (l == r) {
        F[l][r][k] = pow(k + a[l], 2);
        return F[l][r][k];
    }
    F[l][r][k] = DP(l + 1, r, 0) + pow(k + a[l], 2);
    for(int i=l + 1; i <= r; i++)
    if (v[i] == v[l])
        F[l][r][k] = max(F[l][r][k], DP(l + 1, i - 1, 0) + DP(i, r, a[l] + k));
    return F[l][r][k];
}

int main()
{
    scanf("%d\n", &m); scanf("%s", s + 1);
    n = 1; a[1] = 1; v[1] = s[1] - '0';
    for(int i=2; i<=m; i++)
        if (s[i] == s[i - 1]) a[n]++;
        else {
            a[++n] = 1; v[n] = s[i] - '0';
        }
    cout << DP(1, n, 0);
    return 0;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       222;
  so            :       array['0'..'9'] of longint=(0,1,2,3,4,5,6,7,8,9);
  oo            =       1000111000;
var
  f1,f2         :       text;
  a             :       array[1..MAXN] of longint;
  n             :       longint;
  g,count       :       array[1..MAXN,1..MAXN] of longint;
  f             :       array[1..MAXN,1..MAXN,1..MAXN] of longint;
  next          :       array[1..MAXN,0..9] 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;
      c:char;
    begin
      readln(f1,n);
      for i:=1 to n do
        begin
          read(f1,c);
          a[i]:=so[c];
        end;
    end;
procedure init;
    var
      i,j,k:longint;
      x,now:longint;
    begin
      for x:=0 to 9 do
        begin
          now:=0;
          for i:=1 to n do
            begin
              next[i,x]:=now;
              if a[i]=x then now:=i;
            end;
        end; //for x
      for i:=1 to n do count[i,i]:=1;
      for k:=1 to n-1 do
      for i:=1 to n-k do
        begin
          j:=i+k;
          count[i,j]:=count[i,j-1];
          if a[j]=a[i] then count[i,j]+=1;
        end;

      for i:=1 to MAXN do
      for j:=1 to MAXN do
      for k:=1 to MAXN do
        f[i,j,k]:=-oo;
      for i:=1 to MAXN do
      for j:=1 to MAXN do
        g[i,j]:=-oo;
    end;
procedure solve;
    var
      x,i,j,k,l:longint;
    begin
      for i:=1 to n do
        begin
          f[i,i,1]:=0;
          g[i,i]:=1;
        end;
      for k:=1 to n-1 do
      for i:=1 to n-k do
        begin
          j:=i+k;
          f[i,j,1]:=g[i+1,j];
          for l:=count[i,j] downto 2 do
            begin
              if a[j]=a[i] then f[i,j,l]:=f[i,j-1,l-1];
              x:=next[j,a[i]];
              while (x>=i) do
                begin
                  if count[i,x]<l then break;
                  f[i,j,l]:=max(f[i,j,l],f[i,x,l]+g[x+1,j]);
                  x:=next[x,a[i]];
                end;
            end; //for l
          for l:=count[i,j] downto 1 do
            g[i,j]:=max(g[i,j],f[i,j,l]+l*l);
        end; //for i
      writeln(f2,g[1,n]);
    end;

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

Code mẫu của ll931110

{$inline on}
program CUTSEG;
uses math;
const
  input  = '';
  output = '';
  maxn = 204;
  maxv = 10000000;
var
  a: array[1..maxn] of longint;
  F: array[0..maxn,0..maxn,0..maxn] of longint;
  G: array[0..maxn,0..maxn] of longint;
  n: longint;
  fi,fo: text;

procedure openfile;inline;
begin
  assign(fi, input);  reset(fi);
  assign(fo, output);  rewrite(fo);
end;

procedure closefile;inline;
begin
  close(fo);
  close(fi);
end;

procedure init;inline;
var
  i: longint;
  ch: char;
begin
  readln(fi, n);
  for i := 1 to n do
    begin
      read(fi, ch);
      a[i] := ord(ch) - ord('0');
    end;
end;

procedure dp;inline;
var
  i,j,t,s: longint;
  len: longint;
  k: longint;
  flag: boolean;
begin
  for i := 0 to n do
    for j := 0 to n do
      for t := 0 to n do F[i,j,t] := -maxv;

  for i := 1 to n do
    begin
      F[i,i,1] := 0;
      G[i,i] := 1;
    end;

    for len := 1 to n - 1 do
      for i := 1 to n - len + 1 do
        begin
          j := i + len;
          k := 0;
          for s := i to j do
            if a[s] = a[i] then inc(k);

          for t := 1 to k do
            begin
                  //Keep the last element
                  if (a[j] = a[i]) and (F[i,j,t] < F[i,j - 1,t - 1]) and (t > 1)
                    then F[i,j,t] := F[i,j - 1,t - 1];

                  //Remove
                  for s := i to j - 1 do
                    if F[i,j,t] < F[i,s,t] + G[s + 1,j]
                      then F[i,j,t] := F[i,s,t] + G[s + 1,j];
            end;

          G[i,j] := F[i,j,1] + 1;
          for t := 2 to k do
              if G[i,j] < F[i,j,t] + sqr(t)
                then G[i,j] := F[i,j,t] + sqr(t);
        end;

  writeln(g[1,n]);
end;

begin
  openfile;
  init;
  dp;
end.