形式化题目

给定长度为 $n$ 的大写字母串 $S$。折叠序列按三条规则生成，同时给出展开方式：

1. 单个字符 c 是折叠序列，展开为 c；
2. 若 $S,Q$ 都是折叠序列，则 $SQ$ 是折叠序列，展开为二者展开结果的首尾相接；
3. 若 $S$ 是折叠序列、整数 $X>1$，则 X(S) 是折叠序列，展开为 $S$ 的展开结果重复 $X$ 次。

注意规则 3 里 $X$ 必须大于 $1$，1(A) 不是合法折叠串。

求展开结果恰为 $S$ 的折叠序列中，字符数最少的一个（答案不唯一时输出任意一个）。

样例输入 AAAAAAAAAABABABCCD（$n = 18$）的一个最优答案是 9(A)3(AB)CCD，长度 $12$，比原串短 $6$ 个字符。答案可能不唯一：串只含 10 个 A 时，10(A) 与 A9(A) 都是长度为 $5$ 的最优解。

正解

思路

朴素做法与瓶颈

最直接的做法是按定义递归地构造折叠串：枚举把当前串切成两段的所有位置，再枚举所有可能的循环节长度，取展开后长度最小的那个。可行方案的数量随串长指数增长，$n = 100$ 时完全不可行。

瓶颈其实不在枚举的数量级上，而在决策的层次上：与其枚举折叠串，不如直接问“区间 $[i,j]$ 的最短折叠串有多长”。

关键观察：语法树最外层只有两种可能

任何折叠序列都可以看成一棵语法树，内部结点只有两种：

• 拼接结点：由规则 2 产生；
• 重复结点：由规则 3 产生。

于是对于 $S[i..j]$ 的任意一个最优折叠串，它最外层必然是下面两种情形之一：

• 最外层是拼接：存在断点 $k$，$[i,j]$ 被切成 $[i,k]$ 和 $[k+1,j]$ 两段，两段各自折叠，总长度等于两段长度之和。两段互不影响，所以各自取最短即可。
• 最外层是重复：存在块长 $p$，$S[i..j]$ 正好是 $S[i..i+p-1]$ 原样重复 $L/p$ 次（$L = j-i+1$，$p \mid L$）。此时折叠串形如 X(Q)，其中 $X = L/p$，$Q$ 是块自己的折叠串。

这样就把“枚举折叠串”换成了“在区间上做决策”，而所有决策都只依赖更短的区间，可以按区间长度从小到大递推。

状态与转移

设 $f_{i,j}$ 表示 $S[i..j]$ 折叠后的最少字符数。

其中 $L = j-i+1$。重复候选里的三项分别是：块的折叠长度、重复次数的十进制位数、一对括号。

判定“$S[i..j]$ 以 $p$ 为循环节”只需要一次切片比较：$S[i..j-p] = S[i+p..j]$ 等价于对全部 $i \leqslant t \leqslant j-p$ 都有 $S[t] = S[t+p]$，这正好刻画了“长度 $p$ 的块原样重复整次”。

两个容易写错的点

第一，括号里要放块的最优折叠，而不是块本身。 例如 ABABABAB：

• 2(ABAB) 长 $8$，等于原文，没有收益；
• 2(2(AB)) 长 $7$，才是最优。

所以重复候选的块内代价必须写成 $f_{i,i+p-1}$。

第二，折叠不一定更短，必须和拼接一起取最小值。 规则 3 要求 $X > 1$，折叠本身要付出“括号 $+2$、重复次数位数”的代价：

• ABCDEFGHIJKLMNOPQRSTUVWXYZ 没有周期性，压根无法折叠；
• 10 个 A 折成 10(A) 长 $5$，与 A9(A)（$1 + 4$）打平；
• 11 个 A 时 11(A) 长 $5$，才严格优于 A10(A)。

因此循环节 $p$ 只取到 $L/2$（保证 $L/p \geqslant 2$），且重复候选与拼接候选取 $\min$，用“严格更小才替换决策”的写法在平手时保留拼接。

用样例走一遍这张表

样例 S = $ `AAAAAAAAAABABABCCD` 中几个关键区间的 $f 值、最优决策和对应的最优串如下（为了让读者能查表，这里列的是区间 $[i,j]$，不列完整的 $18 \times 18$ 表格）：

读表时注意两点：$[0,9]$ 处 10(A) 与 A9(A) 长度打平，DP 保留了拼接决策，所以答案是 A9(A) 而不是 10(A)，两者都是合法最优解；$[9,14]$ 的 ABABAB 折成 3(AB) 而不是 3(3(A...)) 之类，是因为它的循环节长度只能是 $2$ 或 $1$，$p=2$ 时块 AB 已经最短。

还原答案串

只算出最短长度还不够，要输出具体串，所以 DP 时额外记录两个决策表：

• cut[i][j]：拼接决策的断点 $k$；
• rep[i][j]：重复决策的块长 $p$，$0$ 表示这一段不做整体折叠。

从 $[0,n-1]$ 递归展开：若 rep[i][j] != 0，输出 L/p 加括号，括号里递归展开块 $[i, i+p-1]$；否则按 cut[i][j] 把区间拆成两半分别展开，结果相接。两种情形都严格使用更短的区间，递归深度不超过 $n$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 字符串折叠：区间 DP + 按决策还原最短折叠串
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 512;

char s[MAXN];
int f[MAXN][MAXN];   // f[i][j]：s[i..j] 展开前的最少字符数
int cut[MAXN][MAXN]; // cut[i][j]：拼接时的断点（左半段的右端点）
int rep[MAXN][MAXN]; // rep[i][j]：整体折叠的循环节长度 p，0 表示不折叠

// 按 DP 记录的决策还原 s[i..j] 的最优折叠串：折叠优先，其次按断点拆两半
string unfold(int i, int j) {
    if (i == j) {
        return string(1, s[i]);
    }
    int p = rep[i][j];
    if (p) {
        int times = (j - i + 1) / p;
        char buf[16];
        sprintf(buf, "%d", times);
        return string(buf) + "(" + unfold(i, i + p - 1) + ")";
    }
    int k = cut[i][j];
    return unfold(i, k) + unfold(k + 1, j);
}

int main() {
    if (scanf("%500s", s) != 1) {
        return 0;
    }
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        f[i][i] = 1;
    }
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i + length - 1 < n; i++) {
            int j = i + length - 1;
            // 拼接：枚举断点取最优（并列时取最小的断点）
            int best = f[i][i] + f[i + 1][j], best_k = i;
            for (int k = i + 1; k < j; k++) {
                int v = f[i][k] + f[k + 1][j];
                if (v < best) {
                    best = v;
                    best_k = k;
                }
            }
            f[i][j] = best;
            cut[i][j] = best_k;
            // 折叠：循环节长度 p 必须整除区间长度，且各块完全相同
            for (int p = 1; p <= length / 2; p++) {
                if (length % p) {
                    continue;
                }
                if (memcmp(s + i, s + i + p, j + 1 - p - i) != 0) {
                    continue;
                }
                int digits = 0, t = length / p;
                while (t) {
                    digits++;
                    t /= 10;
                }
                int total = f[i][i + p - 1] + digits + 2; // 重复次数 + 一对括号
                if (total < f[i][j]) {                    // 严格更短才改写决策
                    f[i][j] = total;
                    rep[i][j] = p;
                }
            }
        }
    }
    string ans = unfold(0, n - 1);
    printf("%s\n", ans.c_str());
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 22:35
# update_at: 2026-10-01 22:35

import sys


def unfold(s: str, i: int, j: int, cut: list[list[int]], rep: list[list[int]]) -> str:
    """按 DP 记录的决策还原 s[i..j] 的最优折叠串：rep 优先，其次按 cut 拆两半。"""
    if i == j:
        return s[i]
    p = rep[i][j]
    if p:  # 整段是一个短块重复 length/p 次，块内继续递归折叠
        cnt = (j - i + 1) // p
        return f"{cnt}({unfold(s, i, i + p - 1, cut, rep)})"
    k = cut[i][j]
    return unfold(s, i, k, cut, rep) + unfold(s, k + 1, j, cut, rep)


def fold(s: str) -> str:
    """区间 DP 求 s 的最短折叠串：先枚举断点拼接，再看整段能否写成 X(...)。"""
    n = len(s)
    f = [[0] * n for _ in range(n)]     # f[i][j]：s[i..j] 展开前的最少字符数
    cut = [[-1] * n for _ in range(n)]  # 拼接时的断点：左半段的右端点
    rep = [[0] * n for _ in range(n)]   # 折叠时的块长 p，0 表示这一段不整体折叠
    for i in range(n):
        f[i][i] = 1                      # 单个字母只能是自己

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # 拼接（定义 2）：枚举断点，左右两半各自最优
            k = min(range(i, j), key=lambda k: f[i][k] + f[k + 1][j])
            f[i][j] = f[i][k] + f[k + 1][j]
            cut[i][j] = k
            # 折叠（定义 3）：枚举块长 p，要求 p 整除 length 且相邻块完全相同；
            # 折叠串是 "重复次数(块的最优折叠)"，所以要额外付出位数 + 一对括号
            for p in range(1, length // 2 + 1):
                if length % p or s[i:j + 1 - p] != s[i + p:j + 1]:
                    continue             # 整段每隔 p 个字符与前面相同，才以 p 为循环节
                total = f[i][i + p - 1] + len(str(length // p)) + 2
                if total < f[i][j]:      # 严格更短才改写决策，平手时保留拼接
                    f[i][j], rep[i][j] = total, p
    return unfold(s, 0, n - 1, cut, rep)


def solve() -> None:
    s = sys.stdin.read().strip()
    print(fold(s))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：按长度枚举 $O(n^2)$ 个区间，每个区间枚举断点 $O(n)$，主项为 $O(n^3)$。周期判定只对整除 $L$ 的 $p$ 执行，即每个区间约 $d(L)$ 次（$d$ 为约数个数）$O(L)$ 的切片比较，总量为 $O\bigl(\sum_L (n-L+1)\,L\,d(L)\bigr) = O(n^3 d(n))$，$n \leqslant 100$ 时 $d(n) \leqslant 12$、$d(L)$ 的均值远小于它。整体与标准做法同阶，实测单组数据约 $0.02$ s。
• 空间复杂度：三张 $n \times n$ 的表（长度、拼接断点、折叠块长），即 $O(n^2)$。

总结

本题的核心是把“枚举折叠串”转成“枚举区间决策”。一旦意识到折叠串语法树的最外层只可能是拼接或重复，$S[i..j]$ 的答案就只依赖更短的区间，区间 DP 便自然成立。两个实现陷阱要记住：重复候选的块内代价必须是 $f_{i,i+p-1}$（嵌套折叠常常更优），以及折叠会付出括号和位数的代价，必须与拼接取 $\min$、并把决策记录下来才能输出具体方案。

图示解析

下面这张图概括 $f_{i,j}$ 的两条转移：它把“区间状态”与“拼接 / 重复”两类决策对应起来，也标出了递推的终点（长度 1 的区间）。

flowchart TD
  S["区间 S[i..j]<br/>f[i][j] 最短折叠长度"] --> A["拼接：切在 k<br/>f[i][k] + f[k+1][j]"]
  S --> B["重复：块长 p 是循环节<br/>f[i][i+p-1] + len(L/p) + 2"]
  A --> C["更短的区间"]
  B --> C
  C --> D["长度 1 的区间<br/>f[i][i] = 1"]

读图时关注两点：两条边对应折叠串语法树的两种内部结点；两条边都指向“更短的区间”，所以按长度递增递推不需要考虑循环依赖。

再下面用样例的决策树展示 unfold 的还原过程：每个结点标注区间、$f$ 值和它采用的决策，叶子是单个字符。

1
2
3
4
5[0,17] f=12   拼接，断点 k=8
├── [0,8]  f=4   重复 p=1            → 9(A)
└── [9,17] f=8   拼接，断点 k=14
    ├── [9,14] f=5   重复 p=2        → 3(AB)
    └── [15,17] f=3  拼接            → CCD

把这棵树的叶子从左到右读出来，就得到 9(A)3(AB)CCD，正好是样例输出。这也说明了为什么必须保存决策表：长度相同的拼接与重复（例如 [0,9] 的 10(A) 与 A9(A)）只有靠决策才能还原出确定的串。