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.