折叠序列

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

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

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

包含带个字符的序列被认为是折叠序列，展开它得到的序列为它本身。
如果 S 和 Q 是两个折叠序列，并且 S 可以展开得到 S′，Q 可以展开得到 Q′，则认为 SQ 也是一个折叠序列，并且 SQ 展开得到 S′Q′。
如果 S 是折叠序列，则 X(S) 也是折叠序列，其中 X 为大于 1 的整数。如果 S 展开得到 S′，则 X(S) 展开得到 X 个 S′。
根据定义可以展开任意给出的折叠序列，现在给出原序列，请你将它折叠，并使得折叠序列包含尽可能少的字符数。

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

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

输入样例：
AAAAAAAAAABABABCCD
输出样例：
9(A)3(AB)CCD

“双向”区间DP
一道很明显的区间DP，f[l,r]表示l~r折叠成的最小长度。

转移1：拆成两部分
f[l,r] = min{f[l,k] + f[k+1,r]} 的转移大家都会，就不用多说了。

转移2：循环生成
接下来如果按照一般思路，考虑l~r有哪个子串循环生成，会稍微有点麻烦。

其实动态规划的实现可以有两个方向：

考虑f[l,r]如何得到
考虑f[l,r]可以转移到哪些新的状态
甚至可以把两个方向结合起来——只要按照合理的阶段顺序把所有状态都计算一遍就行了。

所以我们可以改成不断重复f[l,r]，尝试用它更新更长的f[l,ed]，其中ed=r+len,r+2*len,…

详见代码注释。

打印方案
记录转移路径，递归输出即可。

时间复杂度
O(n^3)

C++代码

#include<bits/stdc++.h>
using namespace std;
int f[105][105], p[105][105], n;
char a[105];

bool equals(int r, int ed, int len) { // r,ed往前len个字符是否相同
    for (int i = 0; i < len; i++)
        if (a[r - i] != a[ed - i]) return false;
    return true;
}

void print(int l, int r) {
    if (!p[l][r]) {
        for (int i = l; i <= r; i++) putchar(a[i]);
        return;
    }
    if (p[l][r] > 0) {
        print(l, p[l][r]);
        print(p[l][r] + 1, r);
    } else {
        int len = -p[l][r];
        printf("%d(", (r - l + 1) / len);
        print(l, l + len - 1);
        putchar(')');
    }
}

int main() {
    scanf("%s", a + 1);
    n = strlen(a + 1);
    memset(f, 0x3f, sizeof(f));
    for (int len = 1; len <= n; len++)
        for (int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;
            // [l,r]拆分成两段
            if (len == 1) f[l][r] = 1;
            else for (int k = l; k < r; k++)
                if (f[l][k] + f[k + 1][r] < f[l][r]) {
                    f[l][r] = f[l][k] + f[k + 1][r];
                    p[l][r] = k;
                }
            // [l,r]]重复cnt次生成更长的字符串[l,ed]
            for (int ed = r + len, cnt = 2; ed <= n && equals(r, ed, len); ed += len, cnt++)
                if (f[l][r] + 2 + std::to_string(cnt).length() < f[l][ed]) {
                    f[l][ed] = f[l][r] + 2 + std::to_string(cnt).length();
                    p[l][ed] = -len; // 负数表示由若干个长度为len的子串循环构成
                }
        }
    print(1, n);
}。