回文词是一种对称的字符串——也就是说,一个回文词,从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串,通过插入若干字符,都可以变成一个回文词。你的任务是写一个程序,求出将给定字符串变成回文词所需插入的最少字符数。
比如字符串“Ab3bd”,在插入两个字符后可以变成一个回文词(“dAb3bAd”或“Adb3bdA”)。然而,插入两个以下的字符无法使它变成一个回文词。
program p1327;
type
ty=array[1..5000]of integer;
var
n:integer;
s:ansistring;
f1,f2:ty;
procedure int;
begin
assign(input,‘p1327.in‘);
reset(input);
readln(n);
readln(s);
close(input);
end;
function min(a,b:integer):integer;
begin
min:=a;
if b<min then min:=b;
end;
procedure main;
var
i,j:integer;
begin
for i:=n-1 downto 1 do
begin
f2[i]:=0;
if s[i]=s[i+1] then f2[i+1]:=0 else f2[i+1]:=1;
for j:=i+2 to n do
if s[i]=s[j] then f2[j]:=f1[j-1] else
f2[j]:=min(f2[j-1]+1,f1[j]+1);
f1:=f2;
end;
end;
procedure out1;
begin
assign(output,‘p1327.out‘);
rewrite(output);
writeln(f1[n]);
close(output);
end;
begin
int;
main;
out1;
end.
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。