Description
折叠的定义如下： 1. 一个字符串可以看成它自身的折叠。记作S S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) SSSS…S(X个S)。 3. 如果A A’, BB’，则AB A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) AAACBB，而2(3(A)C)2(B)AAACAAACBB 给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。
Input
仅一行，即字符串S，长度保证不超过100。
Output
仅一行，即最短的折叠长度。
Sample Input
Sample Output
HINT
一个最短的折叠为：2(NEERC3(YES))
题解
令$f_{i,j}$为[i,j)这一段字符串的最短折叠长度。
那么，显而易见的有
$$f_{i,i+1}=1$$
$$f_{i,j}=minleft(min{f_{i,k} +f_{k,j}mid i < k < j}, min{f_{i,k} + 2 + num((j - i) / (k - i)) mid i < k < j, S_{i,j} = frac{j-i}{k-i}S_{i,k}}right)$$
其中$num(x)$表示$x$的十进制位数， $S_{i,j}$表示字符串中i到j的一部分。
那么，应该如何判断$S_{i,j}$是否由$S_{i,k}$重复得到呢？
比较$S_{i,j-k}$和$S_{i+k,j}$即可。
暴力比较就好了。
时间复杂度$O(n^3logn)$
咦，为什么是这个复杂度（不想看请跳过）？
对于每一个长度$len$，都有$n-len+1$个长为$len$的区间，每个区间所需要的字符比较次数至多为
$$sum_{d|len}(len-d)$$
那么总比较次数至多为
$$begin{aligned}
sum_{l=1}^n(n-l+1)sum_{d|l}(l-d) &leq sum_{l=1}^nnsum_{d|l}l\
&= nsum_{l=1}^nlsum_{d|l}1\
&= nsum_{d=1}^nsum_{d|l, 1 leq l leq n}l\
&= nsum_{d=1}^ndsum_{l'=1}^{lfloorfrac{n}drfloor}l'\
&= nsum_{d=1}^ndfrac{lfloorfrac{n}drfloorleft(lfloorfrac{n}drfloor+1right)}2\
&leq nsum_{d=1}^nfrac{nleft(frac{n}d+1right)}2\
&backsim frac{n^3}2sum_{d=1}^nfrac{1}d\
&=O(n^3logn)end{aligned}$$
所以暴力比较只多了一个$log$，可以接受。
附代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
using std::min;
char s[105];
inline bool eq(int b1, int b2, int len) {
return !strncmp(s + b1, s + b2, len);
}
inline int wei(int x) {
int t = 1;
while (x /= 10) ++t;
return t;
}
int f[105][105];
int main() {
scanf("%s", s);
int n = strlen(s);
for (int len = 1; len <= n; ++len)
for (int i = 0; i + len <= n; ++i) {
int j = i + len;
f[i][j] = len;
for (int k = i + 1; k < j; ++k) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
if (!(len % (k - i)) && eq(i, k, j - k))
f[i][j] = min(f[i][j], f[i][k] + 2 + wei(len / (k - i)));
}
}
printf("%dn", f[0][n]);
return 0;
}
- 还没有人评论，欢迎说说您的想法！
客服
