记录编号	3697	评测结果	AAAAAAAAAA
题目名称	[LOL2000] 回文词	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	Pascal	运行时间	3.668 s
提交时间	2008-10-09 12:53:47	内存使用	0.12 MiB

program noip5_2;
 var
    s1,s2:array[1..5000] of char;
    f,g:array[0..5000] of integer;
    n:integer;

procedure init;
 var
    i:integer;
 begin
  readln(n);
  for i:=1 to n do
    begin
    read(s1[i]);
    s2[n-i+1]:=s1[i]
    end;
 end;

procedure main;
 var
    i,j:integer;
 begin
  for i:=1 to n do
   for j:=1 to n do
    begin
    if odd(i)
    then begin
         f[j]:=f[j-1];
         if g[j]>f[j] then f[j]:=g[j];
         if s1[i]=s2[j]
         then if g[j-1]+1>f[j]
              then f[j]:=g[j-1]+1
         end
    else begin
         g[j]:=g[j-1];
         if f[j]>g[j] then g[j]:=f[j];
         if s1[i]=s2[j]
         then if f[j-1]+1>g[j]
              then g[j]:=f[j-1]+1
         end
    end;
  if odd(n) then writeln(n-f[n])
            else writeln(n-g[n]);
 end;

begin
 assign(input,'palin.in');
 assign(output,'palin.out');
 reset(input); rewrite(output);
 init;
 main;
 close(input); close(output);
end.