Description
给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以(但不必)包含大写字母R与M,其中M标记重复串的开始,R重复从上一个M(如果当前位置左边没有M,则从串的开始算起)开始的解压结果(称为缓冲串)。 bcdcdcdcd可以压缩为bMcdRR,下面是解压缩的过程: 另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。Input输入仅一行,包含待压缩字符串,仅包含小写字母,长度为n。Output输出仅一行,即压缩后字符串的最短长度。Sample InputbcdcdcdcdxcdcdcdcdSample Output12HINT在第一个例子中,解为aaaRa,在第二个例子中,解为bMcdRRxMcdRR。 【限制】 50%的数据满足:1<=n<=20 100%的数据满足:1<=n<=50 100%的数据满足:1<=n<=50
区间dp
f[l,r,k]表示区间[l,r]中间是否有M时的最短长度(一个是可能有,一个是一定没有,前面默认有一个M,合并的时候要记得补上)
1 var 2 flag:array[0..50,0..50,0..50,0..50]of boolean; 3 f:array[0..50,0..50,0..1]of longint; 4 n:longint; 5 s:string; 6 7 procedure init; 8 var 9 i,j,k:longint;10 begin11 readln(s);12 for i:=1 to length(s)-1 do13 for j:=i+1 to length(s) do14 if s[i]=s[j] then flag[i,i,j,j]:=true;15 for i:=1 to length(s)-1 do16 for j:=i+1 to length(s) do17 for k:=1 to length(s)-j do18 if flag[i,i+k-1,j,j+k-1] and (s[i+k]=s[j+k]) then flag[i,i+k,j,j+k]:=true;19 end;20 21 function min(x,y:longint):longint;22 begin23 if x>1,i+k>>1+1,i+k] then43 begin44 f[i,i+k,1]:=f[i,i+k>>1,0]+1;45 f[i,i+k,0]:=f[i,i+k,1];46 end;47 for j:=i to i+k-1 do48 begin49 f[i,i+k,0]:=min(f[i,i+k,0],f[i,j,0]+i+k-j);50 f[i,i+k,1]:=min(f[i,i+k,1],f[i,j,1]+f[j+1,i+k,1]+1);51 end;52 f[i,i+k,1]:=min(f[i,i+k,0],f[i,i+k,1]);53 end;54 writeln(f[1,n,1]);55 end;56 57 begin58 init;59 dp;60 end.