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 happyboy99x

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cassert>
using namespace std;

const int N = 2000, C = 256;
int next[N][C], prev[N][C], f[N][N][2], n;
string s;

void enter() {
    cin >> n;
    getline(cin, s);
    getline(cin, s);
}

void init() {
    fill_n(next[n - 1], C, -1);
    next[n - 1][s[n - 1]] = n - 1;
    for(int i = n - 2; i >= 0; --i) {
        copy(next[i + 1], next[i + 1] + C, next[i]);
        next[i][s[i]] = i;
    }
    fill_n(prev[0], C, -1);
    prev[0][s[0]] = 0;
    for(int i = 1; i < n; ++i) {
        copy(prev[i - 1], prev[i - 1] + C, prev[i]);
        prev[i][s[i]] = i;
    }
}

void dp() {
    for(int i = n - 1; i >= 0; --i)
        for(int j = i + 1; j < n; ++j)
            if(s[i] == s[j]) {
                f[i][j][1] = f[i + 1][j - 1][0] + 2;
                f[i][j][0] = max(f[i + 1][j][0], f[i][j - 1][0]);
            } else {
                f[i][j][0] = f[i + 1][j - 1][1] + 2;
                f[i][j][1] = max(f[i + 1][j][1], f[i][j - 1][1]);
            }
}

string tr[N][N][2];

string trace(int i, int j, int k) {
    if(f[i][j][k] == 0) return "";
    if(tr[i][j][k] != "") return tr[i][j][k];
    string &res = tr[i][j][k];
    if(k == 0) {
        for(int c1 = 0; c1 < C; ++c1) {
            int p = next[i][c1];
            if(p == -1) continue;
            for(int c2 = 0; c2 < C; ++c2) if(c1 != c2) {
                int q = prev[j][c2];
                if(q == -1 || f[p][q][0] != f[i][j][0]) continue;
                string temp = char(c1) + trace(p + 1, q - 1, 1) + char(c2);
                if(res == "" || temp < res) res = temp;
            }
            if(res != "") return res;
        }
    } else {
        for(int c = 0; c < C; ++c) {
            int p = next[i][c], q = prev[j][c];
            if(p == -1 || q == -1 || f[p][q][1] != f[i][j][1]) continue;
            return res = char(c) + trace(p + 1, q - 1, 0) + char(c);
        }
    }
    assert(false);
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    init();
    dp();
    cout << trace(0, n - 1, 1) << '\n';
    return 0;
}

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>
#include <climits>
#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 TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#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 = 2015;
const int DIFF = 1;

using namespace std;

char s[N], str[N];
int f[N][N][2], rightBound[N];
VI pos[26];
int n, ans, cutOff;

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

void dpPreProcess() {
    REPD(i, n, 1) REP(j, i + 1, n) {
        REP(k, 0, 1) f[i][j][k] = max(f[i + 1][j][k], f[i][j - 1][k]);
        if (s[i] == s[j]) {
            f[i][j][!DIFF] = f[i + 1][j - 1][DIFF] + 2;
            f[i][j][DIFF] = max(f[i + 1][j][DIFF], f[i][j - 1][DIFF]);
        }
        else {
            f[i][j][DIFF] = f[i + 1][j - 1][!DIFF] + 2;
            f[i][j][!DIFF] = max(f[i + 1][j][!DIFF], f[i][j - 1][!DIFF]);
        }
    }
}

bool sat(int l, int r, int c, int status, int need, int &newL, int &newR) {
    //can c be chosen in range [l..r] to have answer == need
    if (status != DIFF) {
        int ll = lower_bound(ALL(pos[c]), l) - pos[c].begin();
        int rr = upper_bound(ALL(pos[c]), r) - pos[c].begin() - 1;
        if (ll >= SZ(pos[c]) || rr < 0) return 0;
        newL = pos[c][ll], newR = pos[c][rr];
        return f[newL][newR][status] >= need;
    }
    //now the status is DIFF
    int ll = lower_bound(ALL(pos[c]), l) - pos[c].begin();
    if (ll >= SZ(pos[c])) return 0;
    int maxR = 0;
    FOR(cc, 0, 26) if (cc != c && !pos[cc].empty()) {
        int rr = upper_bound(ALL(pos[cc]), r) - pos[cc].begin() - 1;
        if (rr < 0) continue;
        newL = pos[c][ll], newR = pos[cc][rr];
        if (f[newL][newR][status] >= need) maxi(maxR, newR);
    }
    if (maxR) {newR = maxR; return 1;}
    return 0;
}

void solveFirstHalf() {
    int half = ans / 2;
    int l = 1, r = n, need = ans, newL, newR;
    rightBound[0] = r;
    REP(i, 1, half) {
        int status = (i & 1) ^ 1;
        FOR(c, 0, 26)
            if (sat(l, r, c, status, need, newL, newR)) {
                str[i] = 'a' + c;
                break;
            }
        need -= 2;
        l = newL + 1, r = newR - 1;
        rightBound[i] = newR;
    }
    cutOff = l;
}

void solveSecondHalf() {
    int half = ans / 2;
    int status = half & 1, l = cutOff, r = rightBound[half];
    REP(i, half + 1, ans) {
        status ^= 1;
        if (status != DIFF) {
            str[i] = str[ans - i + 1];
            char c = str[i] - 'a';
            l = pos[c][lower_bound(ALL(pos[c]), l) - pos[c].begin()] + 1;
        }
        else {
            FOR(c, 0, 26)
            if ('a' + c != str[ans - i + 1]) {
                if (pos[c].empty()) continue;
                int ll = lower_bound(ALL(pos[c]), l) - pos[c].begin();
                if (ll >= SZ(pos[c]) || pos[c][ll] > r) continue;
                str[i] = 'a' + c;
                l = pos[c][ll] + 1;
                break;
            }
        }
        r = rightBound[ans - i];
    }
}

void writeAnswer() {
    ans = f[1][n][!DIFF];
    solveFirstHalf();
    solveSecondHalf();
}

int main() {
    scanf("%d\n", &n); scanf("%s", s + 1);
    REP(i, 1, n) pos[s[i] - 'a'].PB(i);
    dpPreProcess();
    writeAnswer();
    printf("%s\n", str + 1);
    return 0;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       2011;
var
  f1,f2         :       text;
  n             :       longint;
  s,kq          :       array[1..MAXN] of char;
  d             :       array[1..MAXN,1..MAXN,1..2] of longint;
  next,prev     :       array[-1..MAXN,#1..#255] of longint;
  prev2         :       array[-1..MAXN,#1..#255] of longint;
  right         :       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
      readln(f1,n);
      for i:=1 to n do
       read(f1,s[i]);
    end;
procedure solve;
    var
      i,j,k:longint;
      ch:char;
    begin
      for k:=1 to n-1 do
      for i:=1 to n-k do
        begin
          j:=i+k;

          if s[i]<>s[j] then d[i,j,1]:=d[i+1,j-1,2]+2
          else d[i,j,1]:=max(d[i+1,j,1],d[i,j-1,1]);

          if s[i]=s[j] then d[i,j,2]:=d[i+1,j-1,1]+2
          else d[i,j,2]:=max(d[i+1,j,2],d[i,j-1,2]);
        end;

      for ch:=#1 to #255 do
        begin
          next[n+1,ch]:=n+1;
          for i:=n downto 1 do
            if s[i]=ch then next[i,ch]:=i
            else next[i,ch]:=next[i+1,ch];

          prev[0,ch]:=0;
          for i:=1 to n do
            if s[i]=ch then prev[i,ch]:=i
            else prev[i,ch]:=prev[i-1,ch];

          prev2[0,ch]:=0;
          for i:=1 to n do
            if s[i]<>ch then prev2[i,ch]:=i
            else prev2[i,ch]:=prev2[i-1,ch];
        end;
    end;
procedure ans;
    var
      ch:char;
      best,i,j,need,now,tt,luu:longint;
    begin
      need:=d[1,n,2]; best:=need;
      i:=1; j:=n; tt:=2;
      for now:=1 to best>>1 do
        for ch:=#1 to #255 do
          if ((tt=2) and (next[i,ch]<=n) and (prev[j,ch]>0) and (d[next[i,ch],prev[j,ch],2]=need))
          or ((tt=1) and (next[i,ch]<=n) and (prev2[j,ch]>0) and (d[next[i,ch],prev2[j,ch],1]=need)) then
            begin
              kq[now]:=ch; right[now]:=j;
              i:=next[i,ch]+1; if tt=2 then j:=prev[j,ch]-1 else j:=prev2[j,ch]-1;
              dec(need,2); tt:=3-tt;
              break;
            end;
      now:=i;
      for i:=1 to best>>1 do write(f2,kq[i]);
      for i:=best>>1 downto 1 do
      if tt=2 then
        begin
          tt:=1;
          luu:=-1;
          for j:=now to right[i] do
          if s[j]<>kq[i] then
            if (luu=-1) or (s[j]<s[luu]) then luu:=j;
          now:=luu+1; write(f2,s[luu]);
        end
      else
        begin
          tt:=2;
          write(f2,kq[i]);
          now:=next[now,kq[i]]+1;
        end;
    end;

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