【题意】
给定一个长度为n(n<=5000)的字符串,求最少加入多少个字符可以使他变为回文串
【输入】
第一行一个n
接下来一行n个字符表示字符串
【输出】
一个数字,表示最少加入多少个字符可以使他变为回文串
将原串反过来求两串的最长公共子序列
然后拿n减去即可
program poj1159; var n,i,j,k,o:longint; s1,s2:ansistring; f:array [0..1,0..5001] of longint; begin readln(n); readln(s1); for i:=1 to n do s2:=s2+s1[n-i+1]; fillchar(f,sizeof(f),0); o:=0; for i:=1 to n do begin o:=1-o; for j:=1 to n do begin f[o,j]:=f[1-o,j]; if f[o,j]<f[o,j-1] then f[o,j]:=f[o,j-1]; if (s1[i]=s2[j])and(f[o,j]<f[1-o,j-1]+1) then f[o,j]:=f[1-o,j-1]+1; end; end; writeln(n-f[o,n]); end.