COUNTPL – spoj

Đề 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.