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=1001;
var n,re:longint;
    s:ansistring;
    d:array[1..maxn,1..maxn] of boolean;
    r,l:array[1..maxn] of longint;

procedure rf;
begin
     assign(input,fi); reset(input);
     readln(s);
     n:=length(s);
     close(input);
end;

procedure pr;
var i,len,j,k,z,v:longint;
begin
     re:=0;
     for i:=1 to n do d[i,i]:=true;
     for i:=1 to n-1 do
         if s[i]=s[i+1] then
         begin
              d[i,i+1]:=true; r[i]:=i+2; l[i+1]:=i;
              re:=re+1;
         end;
     for len:=3 to n do
         for i:=1 to n-len+1 do
         begin
              j:=i+len-1;
              if d[i+1,j-1] and (s[i]=s[j]) then
              begin
                   d[i,j]:=true; re:=re+1; if r[i]=0 then r[i]:=j+1;
                   if l[j]=0 then l[j]:=i;
                   continue;
              end;
              if r[i]=0 then z:=i+2 else z:=r[i];
              if l[j]=0 then v:=j-1 else v:=l[j];
                 for k:=z to v do
                     if d[i,k-1] and d[k,j] then
                     begin
                          d[i,j]:=true;
                          if r[i]=0 then r[i]:=k; if l[j]=0 then l[j]:=k;
                          re:=re+1;
                          break;
                     end;
         end;
end;

procedure wf;
begin
     assign(output,fo); rewrite(output);
     writeln(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstring>
#include<cstdio>

const int N = 1000;
char s[N + 1];
bool f[N][N];

int main() {
    scanf("%s", s);
    int n = strlen(s);
    for(int i = 0; i < n; ++i) f[i][i] = true;
    for(int i = 0; i + 1 < n; ++i) f[i][i + 1] = s[i] == s[i + 1];
    for(int i = n - 1; i >= 0; --i)
        for(int j = i + 2; j < n; ++j) {
            f[i][j] = s[i] == s[j] && f[i + 1][j - 1];
            for(int p = i + 1; !f[i][j] && p + 1 < j; ++p)
                f[i][j] |= f[i][p] && f[p + 1][j];
        }
    int res = 0;
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n; ++j)
            if(f[i][j]) ++res;
    printf("%d\n", res);
    return 0;
}

Code mẫu của ladpro98

uses    math;
const   maxN=1001;
        fi='';
var     isPal,check:array[1..maxN,1..maxN] of boolean;
        f:array[0..maxN] of int64;
        n,res:longint;
        a:ansistring;

procedure input;
var     inp:text;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,a);
        close(inp);
        n:=length(a);
end;

procedure init;
var     i,j,t:longint;
begin

        for i:=1 to n do
        begin
                isPal[i,i]:=true;
                for t:=1 to n do
                begin
                        if (t+1>i) or (i+t>n) then break;
                        if a[i-t]=a[i+t] then isPal[i-t,i+t]:=true
                        else break;
                end;
                for t:=1 to n do
                begin
                        if (i<t) or (i+t>n) then break;
                        if a[i-t+1]=a[i+t] then isPal[i-t+1,i+t]:=true
                        else break;
                end;
        end;
end;

procedure dp;
var     i,j,k:longint;
begin

        for i:=1 to n do
        begin
                for j:=i+1 to n do
                begin
                        if isPal[i,j] then
                        begin
                                check[i,j]:=true;
                                continue;
                        end;
                        for k:=j-1 downto i+1 do
                        if isPal[k,j] and (check[i,k-1]) then
                        begin
                                check[i,j]:=true;
                                break;
                        end;
                end;
        end;
end;

procedure output;
var     i,j:longint;
begin
        for i:=1 to n do
        for j:=i+1 to n do
        if check[i,j] then inc(res);
        write(res);
end;

begin
        input;
        init;
        dp;
        output;
end.

Code mẫu của RR

{$MODE OBJFPC}

const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       1011;

var
  f1,f2         :       text;
  n             :       longint;
  s             :       ansistring;
  f             :       array[1..MAXN,1..MAXN] of boolean;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure solve;
    var
      i,j,k,res,x:longint;
    begin
      res:=0;
      for i:=1 to n do
        f[i,i]:=true;
      for i:=1 to n-1 do
        if s[i]=s[i+1] then f[i,i+1]:=true else f[i,i+1]:=false;

      for k:=2 to n-1 do
      for i:=1 to n-k do
        begin
          j:=i+k;
          f[i,j]:=f[i+1,j-1] and (s[i]=s[j]);
        end;

      for k:=2 to n-1 do
      for i:=1 to n-k do
        begin
          j:=i+k;
          if f[i,j] then continue;
          for x:=i+1 to j-2 do
            if f[i,x] and f[x+1,j] then
              begin
                f[i,j]:=true;
                break;
              end;
        end;

      for i:=1 to n-1 do
      for j:=i+1 to n do
        if f[i,j] then inc(res);
      writeln(f2,res);
    end;

begin
  openF;
  readln(f1,s); n:=length(s);
  solve;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <cstring>

bool p[1001][1001];
int n,KQ=0;
char s[1001];

int main()
{
     gets(s);
     n = strlen(s);
     for(int i = 0;i<n;i++) p[i][i] = true;
     for(int i = 0;i<n-1;i++)
     {
        if(s[i]==s[i+1]) p[i][i+1] = true;
        else p[i][i+1] = false;
     }

     for(int i = 2;i<=n-1;i++)
         for(int j = 0;j<=n-1-i;j++)
         {
             if(s[j]==s[j+i])
                 p[j][j+i] = p[j+1][j+i-1];
             else p[j][j+i] = false;
         }
     for(int i = 0;i<n;i++) p[i][i] = false;      
     for(int i = 1;i<=n-1;i++)
         for(int j = i-1;j>=0;j--)
             for(int u = j;u<=i-1;u++)
                 if(p[j][u]&&p[u+1][i])
                 {
                     p[j][i]= true;
                     break;
                 }
     for(int i = 0;i<n;i++)
         for(int j = i+1;j<n;j++)
             if(p[i][j])
                KQ++;
     printf("%d",KQ);
    // getch();
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<vector>
#define MAX   1111
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
const int mod[]={(int)1e9+21,(int)1e9+7,(int)1e9+9,(int)1e9+33};
const int nmod=2;
const int base=31;
char s[MAX];
int bh[nmod][MAX];
int fh[nmod][MAX];
int pw[nmod][MAX];
int n;
vector<int> paend[MAX];
bool chk[MAX][MAX];
bool pa[MAX][MAX];
void init(void) {
    scanf("%s",s+1);
    n=strlen(s+1);
    REP(j,nmod) {
        pw[j][0]=1;
        FOR(i,1,n) pw[j][i]=(1LL*pw[j][i-1]*base)%mod[j];
        FOR(i,1,n) fh[j][i]=(fh[j][i-1]+1LL*pw[j][i-1]*(s[i]-'a'))%mod[j];
        FORD(i,n,1) bh[j][i]=(bh[j][i+1]+1LL*pw[j][n-i]*(s[i]-'a'))%mod[j];
    }
}
bool palin(int l,int r) {
    if (l==r) return (false);
    //printf("CHECK %d %d\n",l,r);
    REP(i,nmod) {
        int x=(fh[i][r]-fh[i][l-1]+mod[i])%mod[i];
        int y=(bh[i][l]-bh[i][r+1]+mod[i])%mod[i];
        if (l-1<n-r) x=(1LL*x*pw[i][n-r-l+1])%mod[i];
        if (l-1>n-r) y=(1LL*y*pw[i][r+l-n-1])%mod[i];
        //if ((x-y)%mod[i]!=0) printf("FAIL %d\n",i);
        if ((x-y)%mod[i]!=0) return (false);
    }
    //printf("OK\n");
    return (true);
}
void count(void) {
    FOR(i,1,n) FORD(j,i,1) {
        pa[j][i]=palin(j,i);
        if (pa[j][i]) paend[i].push_back(j);
    }
    int res=0;
    FOR(d,1,n-1) FOR(l,1,n-d) {
        int r=l+d;
        if (pa[l][r]) {
            chk[l][r]=true;
            res++;
            continue;
        }
        FORE(it,paend[r]) {
            if (*it<=l+1) break;
            if (chk[l][*it-1]) {
                chk[l][r]=true;
                res++;
                break;
            }
        }
    }
    printf("%d",res);
}
int main(void) {
    init();
    count();
    return 0;
}

Code mẫu của khuc_tuan

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

char a[1010];
int n;
vector<int> ds[1010];
bool F[1010][1010];

int main() {
    gets(a);
    n = strlen(a);
    for(int i=0;i<n;++i) {
        int tr = i, ph = i;
        while(0 <= tr && ph < n && a[tr]==a[ph]) {
            if(ph-tr+1 >= 2) ds[ph].push_back(tr);
            -- tr;
            ++ ph;
        }
        tr = i;
        ph = i + 1;
        while(0 <= tr && ph < n && a[tr]==a[ph]) {
            if(ph-tr+1 >= 2) ds[ph].push_back(tr);
            -- tr;
            ++ ph;
        }
    }
    for(int i=n-1;i>=0;--i) for(int j=i;j<n;++j) {
        for(int k=(int)ds[j].size()-1;k>=0;--k) {
            int tr = ds[j][k];
            if(F[i][tr-1] || tr==i) {
                F[i][j] = true;
                break;  
            }   
        }   
    }
    int dem = 0;
    for(int i=0;i<n;++i) for(int j=i;j<n;++j) if(F[i][j]) ++dem;
    cout << dem << endl;
    return 0;
}