找循环节时可以用 KMP 优化一下，但是 100 的数据就算暴力也可以轻松过。
1 #include <stdio.h>
2 #include <string.h>
3 #include <algorithm>
4
5 int len;
6 int Mem[120][120], fail[120];
7 char S[120];
8
9 inline int Bitcnt(int v)
10 {
11 int cnt = 0;
12 do ++cnt;
13 while (v /= 10);
14 return cnt;
15 }
16
17 int dfs(int L, int R)
18 {
19 if (Mem[L][R]) return Mem[L][R];
20 if (L == R) return Mem[L][R] = 1;
21
22 int i, j;
23 Mem[L][R] = R - L + 1;
24
25 //KMP
26 char *tmp_S = S + L - 1;
27 int tmp_len = R - L + 1;
28 fail[1] = j = 0;
29 for (i = 2; i <= tmp_len; ++i) {
30 while (j && tmp_S[j + 1] != tmp_S[i])
31 j = fail[j];
32 if (tmp_S[j + 1] == tmp_S[i]) ++j;
33 fail[i] = j;
34 }
35 int tmp_cut = tmp_len - fail[tmp_len];
36 if (tmp_len != tmp_cut && !(tmp_len % tmp_cut))
37 Mem[L][R] = std::min(Mem[L][R], Bitcnt(tmp_len / tmp_cut) + 2 + dfs(L, L + tmp_cut - 1));
38
39 for (i = L; i < R; ++i)
40 Mem[L][R] = std::min(Mem[L][R], dfs(L, i) + dfs(i+1, R));
41
42 return Mem[L][R];
43 }
44
45 int main()
46 {
47 scanf("%s", S + 1);
48 len = strlen(S + 1);
49 printf("%d\n", dfs(1, len));
50 return 0;
51 }
NKOJ2388
| 字符串折叠 | |
|
问题描述
折叠的定义如下：
1. 一个字符串可以看成它自身的折叠。记作S =S
2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
3. 如果A = A’, B=B’，则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。
输入格式
仅一行，即字符串S，长度保证不超过100。
输出格式
仅一行，即最短的折叠长度
样例输入
NEERCYESYESYESNEERCYESYESYES
样例输出
14