Đề bài: http://vn.spoj.com/problems/COUNTPL/
Thuật toán:
- Tính trước mảng pan[i][j] = true nếu xâu s[i..j] là palindrome và ngược lại
- Gọi f[i][j]=true nếu xâu s[1..i] có thể chia làm j xâu palindrome và ngược lại
- Code đoạn tính f[i][j] cho các bạn dễ hiểu:
f[0,0] := true; res := oo; for i:=1 to n do for j:=1 to i do begin for k:=i downto 1 do begin if pan[k,i] then if f[k-1,j-1] then f[i,j] :=true; end; if i=n then if f[i,j] then res := min(res,j); end; |
Code:
uses math; const fi=''; fo=''; maxn=300; oo=1000; var pan :array[1..maxn,1..maxn] of boolean; i,j,n :longint; s :string; f :array[0..maxn,0..maxn] of boolean; res :longint; procedure enter; begin assign(input,fi);reset(input); readln(s); close(input); end; function check(i,j :longint):boolean; var tg :string; begin tg := copy(s,i,j-i+1); for i :=1 to length(tg) div 2 do if tg[i]<>tg[length(tg)-i+1] then exit(false); exit(true); end; procedure process; var i,j,k :longint; begin n := length(s); for i:=1 to n do for j:=i to n do if check(i,j) then pan[i,j] := true; f[0,0] := true; res := oo; for i:=1 to n do for j:=1 to i do begin for k:=i downto 1 do begin if pan[k,i] then if f[k-1,j-1] then f[i,j] :=true; end; if i=n then if f[i,j] then res := min(res,j); end; end; procedure print; begin assign(output,fo);rewrite(output); writeln(res); close(output); end; begin enter; process; print; end. |
Speak Your Mind