hiho一下第160周《String Folding》题目分析

16
4

本题是一道非常经典的动态规划题目。

设S[1..n]是一个长度为n的字符串,best(S)是S的最短压缩,那么best(S)可能为三种形式中最短的一种:

1) 原串形式:best(S) = S。例如CCD最短压缩就是CCD本身。

2) 拼接形式: best(S[1..n]) = best(S[1..i]) + best(S[i+1..n])。

例如AAAAAAAAAABABABCCD的最短压缩9(A)3(AB)CCD,可以视为由best(AAAAAAAAAABABAB) = 9(A)3(AB) 和 best(CCD) = CCD 拼接而成。

3) 嵌套形式: best(S[1..n]) = k的位数 + 2 + best(S[1..n/k]),其中k>1且是n的约数,S是由k个S[1..n/k]循环拼接而成。

也就是说S[1..n]可以表示成k(s[1..n/k]),这时k(s[1..n/k])的长度是k的位数 + 一对括号的长度2 + best(S[1..n/k)

例如HIHOHIHOCODERHIHOHIHOCODER有循环节HIHOHIHOCODER,所以best(HIHOHIHOCODERHIHOHIHOCODER) = 1 + 2 + (best(HIHOHIHOCODER))。

write answer 切换为英文 切换为中文


转发分享