传送门 明显区间dp f[i][j]表示i到j一段的最少涂色次数 枚举是直接修改还是两边组合。
uses math;
var
s:
string;
f:
array [
0..
55,
0..
55]
of longint;
n,i,j,k,p:longint;
begin
readln(s); n:=length(s);
fillchar(f,sizeof(f),
1);
for i:=
1 to n
do f[i,i]:=
1;
for i:=
2 to n
do
for j:=
1 to n-i+
1 do
begin
if s[j]=s[j+i-
1]
then p:=
0 else p:=
1;
f[j,j+i-
1]:=min(f[j,j+i-
2],f[j+
1,j+i-
1])+p;
for k:=j
to j+i-
2 do f[j,j+i-
1]:=min(f[j,j+i-
1],f[j,k]+f[k+
1,j+i-
1]);
end;
write(f[
1,n]);
end.
转载请注明原文地址: https://ju.6miu.com/read-667812.html
