记录编号	5894	评测结果	AAAAAAAAAA
题目名称	[LOL2000] 回文词	最终得分	100
用户昵称	zpl123	是否通过	通过
代码语言	Pascal	运行时间	3.159 s
提交时间	2008-10-29 13:48:50	内存使用	95.50 MiB

program palin;

var
f:array[1..5000,0..5000]of longint;
s:array[1..5000]of char;
l:longint;


procedure init;
var
i:longint;
begin
assign(input,'palin.in');
reset(input);
assign(output,'palin.out');
rewrite(output);
readln(l);
for i:=1 to l do read(s[i]);
close(input);
fillchar(f,sizeof(f),0);
for i:=1 to l do f[1,i]:=0;
for i:=1 to l-1 do
 if s[i]=s[i+1] then f[2,i]:=0 else f[2,i]:=1;
end;

procedure main;
var
i,j:longint;
begin
for i:=3 to l do
 for j:=1 to l-i+1 do
 begin
 if s[j]=s[i+j-1] then f[i,j]:=f[i-2,j+1]
 else
 if f[i-1,j]<f[i-1,j+1] then f[i,j]:=f[i-1,j]+1
 else f[i,j]:=f[i-1,j+1]+1;
 end;
end;

begin
init;
main;
writeln(f[l,1]);
close(output);
end.