var s: AnsiString; n, _, i, j, l: integer; huiwen: array [1..1000, 1..1000] of boolean; //s[i,j]是否为回文串 dp: array [0..1000] of integer; //一定从0开始,否则当整串为回文串时就考虑不到了。
functionmin(x,y: integer): integer; begin if x<y thenexit(x) elseexit(y); end;
procedureprocess(i,j: integer);//对回文串进行预处理 var mid: Integer; x,y: integer; begin if j = i then begin huiwen[i,j] := true; exit; end; mid := i + (j-i+1) shr1; x := i; y := j; while (x <= mid) and (s[x] = s[y]) do begin inc(x); dec(y); end; huiwen[i, j] := x > mid; end;
begin //assign(input, 'main.in'); reset(input); //assign(output, 'main.out'); rewrite(output); readln(n); for _ := 1to n do begin readln(s); l := length(s); //Pre-process fillchar(huiwen, sizeof(huiwen), 0); for i := 1to l do for j := i to l do//一定是从i开始,这个错卡了我很久。 process(i, j); //DP for i := 1to l do begin dp[i] := i; for j := 0to i-1do if huiwen[j+1, i] then dp[i] := min(dp[i], dp[j]+1); end; write(dp[l]); {if _ <>n then }writeln; //吐槽一下:一开始我还谨慎地加上这句以避免行末回车,没想到UVa居然报错了。。看来UVa的比较算法还有待改进啊。 end;
OOPS!
A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.