题目描述

比尔正在试图用折叠重复子序列的方式紧凑的表示由大写字母 A 到 Z 组成的字符序列。

例如，表示序列 AAAAAAAAAABABABCCD 的一种方式是 10(A)2(BA)B2(C)D。

他通过以下方式定义了折叠的字符序列以及它们的展开变换：

1. 包含单个字符的序列被认为是折叠序列，展开它得到的序列为它本身。
2. 如果 $S$ 和 $Q$ 是两个折叠序列，并且 $S$ 可以展开得到 $S'$，$Q$ 可以展开得到 $Q'$，则认为 $SQ$ 也是一个折叠序列，并且 $SQ$ 展开得到 $S'Q'$。
3. 如果 $S$ 是折叠序列，则 $X(S)$ 也是折叠序列，其中 $X$ 为大于 1 的整数。如果 $S$ 展开得到 $S'$，则 $X(S)$ 展开得到 $X$ 个 $S'$。

根据定义可以展开任意给出的折叠序列，现在给出原序列，请你将它折叠，并使得折叠序列包含尽可能少的字符数。

输入格式

输入包含一行由大写字母构成的字符序列，序列长度在 $1$ 到 $100$ 之间。

输出格式

输出包含字符数最少的折叠序列，如果答案不唯一则任意输出一个即可。

样例

AAAAAAAAAABABABCCD

9(A)3(AB)CCD

样例解释

原序列

AAAAAAAAAABABABCCD

长度为 18。

折叠表示

一种可能的折叠表示：9(A)3(AB)CCD

展开：

• 9(A) → AAAAAAAAA
• 3(AB) → ABABAB
• CCD → CCD 拼接：AAAAAAAAAABABABCCD，与原序列一致。

折叠序列的字符数为 9（注意：9(A) 是 3 个字符，3(AB) 是 5 个字符，CCD 是 3 个字符，总 3+5+3=11？不对，让我们数一下：9(A)3(AB)CCD：

• 9 1 字符
• ( 1 字符
• A 1 字符
• ) 1 字符 → 9(A) 共 4 字符
• 3 1 字符
• ( 1 字符
• A 1 字符
• B 1 字符
• ) 1 字符 → 3(AB) 共 5 字符
• C 1 字符
• C 1 字符
• D 1 字符 → CCD 3 字符 总 4+5+3=12 字符。

但题目说输出 9(A)3(AB)CCD，所以样例答案就是 12 个字符？原序列长 18，压缩到 12。

但还有更短的表示吗？例如 10(A)2(BA)B2(C)D 长度：

• 10(A)：10 2 字符，( 1, A 1, ) 1 → 5 字符
• 2(BA)：2 1, ( 1, B 1, A 1, ) 1 → 5 字符
• B：1 字符
• 2(C)：4 字符
• D：1 字符 总 5+5+1+4+1=16 字符，比 12 长。

所以 9(A)3(AB)CCD 是一种较优压缩。

数据范围

• 序列长度 $1 \le len \le 100$

算法分析

这是一个区间动态规划问题，要求将给定字符串折叠成最短的表示形式。

状态定义

设 $dp[i][j]$ 表示子串 $s[i..j]$ 的最短折叠表示的长度（字符数）。

转移方程

1. 直接拼接：将子串分成两部分 $[i,k]$ 和 $[k+1,j]$，则 $dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] \}$。

2. 重复模式折叠：如果子串 $s[i..j]$ 可以由一个更短的子串重复多次得到，那么可以用 $X(S)$ 的形式表示。 设子串长度为 $len = j-i+1$，枚举重复单元的长度 $l$，满足 $l$ 整除 $len$，并且子串 $s[i..i+l-1]$ 重复 $len/l$ 次等于 $s[i..j]$。 则折叠表示形式为 $\frac{len}{l}($ + $dp[i][i+l-1]$ + $)$，其长度 = 数字 $\frac{len}{l}$ 的位数 + 2（括号） + $dp[i][i+l-1]$。 即 $dp[i][j] = \min \{ \text{digits}(\frac{len}{l}) + 2 + dp[i][i+l-1] \}$。

注意：如果重复单元本身可以折叠，$dp[i][i+l-1]$ 已经是其最短表示长度。

初始条件

单个字符：$dp[i][i] = 1$。

记录方案

为了输出折叠序列，我们需要记录每个状态的最优表示字符串。可以用一个字符串数组 $ans[i][j]$ 存储 $s[i..j]$ 的最短折叠表示。

在转移时，如果找到更优长度，则更新 $ans[i][j]$。

检查重复

如何快速判断 $s[i..j]$ 是否由 $s[i..i+l-1]$ 重复构成？ 可以比较字符串：对于每个 $l$ 整除 $len$，检查 $s[i..i+l-1]$ 是否重复 $len/l$ 次等于 $s[i..j]$。由于长度 ≤100，可以直接比较。

复杂度

状态数 $O(n^2)$，每个状态转移：

• 枚举分割点 $k$：$O(n)$
• 枚举重复单元长度 $l$：$O(n)$ 总复杂度 $O(n^3)$，对于 $n \le 100$，$100^3 = 10^6$，可以接受。

实现细节

数字位数

函数 digits(x) 返回整数 $x$ 的十进制位数。

检查重复

给定子串 $s[i..j]$ 和长度 $l$，检查是否由 $s[i..i+l-1]$ 重复组成： 对于 $t = 0$ 到 $len-1$，检查 $s[i+t] == s[i + (t \mod l)]$。

更新策略

对于每个状态 $[i,j]$，先初始化为直接拼接（枚举 $k$）得到的最小值，然后尝试重复折叠，如果更优则更新。

输出

最终答案为 $ans[0][n-1]$。

样例验证

对于样例 AAAAAAAAAABABABCCD，通过 DP 可以得到最短表示之一为 9(A)3(AB)CCD。

总结

本题是区间 DP 的经典题目，关键在于处理重复子串的折叠表示。注意数字的位数和括号计入长度，以及如何检查重复模式。