QBPAL - Đếm chuỗi đối xứng

Tác giả: ladpro98

Ngôn ngữ: Pascal

program qbpal;
uses    math;
type    big=string;

const   fi='';
var     s:string;
        f:array[1..123,1..123] of big;
        check:array[1..123,1..123] of boolean;
        n:longint;

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

function plus(a,b:big):big;
var     c:big;
        i,carry,s:longint;
begin
        carry:=0;c:='';
        while  length(a)<length(b) do a:='0'+a;
        while  length(b)<length(a) do b:='0'+b;
        for i:=length(a) downto 1 do
        begin
                s:=ord(a[i])+ord(b[i])+carry-96;
                c:=chr(s mod 10+48) +c;
                carry:=s div 10;
        end;
        if carry>0 then c:='1'+c;
        exit(c);
end;

function sub(a,b:big):big;
var     c:big;
        s,br,i:longint;
begin
        br:=0;
        c:='';
        while  length(a)<length(b) do a:='0'+a;
        while  length(b)<length(a) do b:='0'+b;
        for i:=length(a) downto 1 do
        begin
                s:=ord(a[i])-ord(b[i])-br;
                if s<0 then
                begin
                        s:=s+10;
                        br:=1;
                end
                else
                br:=0;
                c:=chr(s+48)+c;
        end;
        while (length(c)>1) and (c[1]='0') do delete(c,1,1);
        exit(c);
end;

procedure init;
var     i,j:longint;
begin
        for i:=1 to n do
        begin
                f[i,i]:='1';
                check[i,i]:=true;
        end;
        for i:=1 to n-1 do
        begin
                if s[i]=s[i+1] then
                begin
                        f[i,i+1]:='3';
                        check[i,i+1]:=true;
                end
                else
                begin
                        f[i,i+1]:='2';
                        check[i,i+1]:=true;
                end;
        end;
end;

function dp(i,j:longint):big;
var     k:longint;
begin
        if check[i,j] then exit(f[i,j]);
        check[i,j]:=true;
        if s[i]=s[j] then
        f[i,j]:=plus(plus(dp(i+1,j),dp(i,j-1)),'1')
        else
        f[i,j]:=sub(plus(dp(i+1,j),dp(i,j-1)),dp(i+1,j-1));
        exit(f[i,j]);
end;

begin
        input;
        init;
        write(dp(1,n));
end.

Download