一道奇怪的题目。

题目要让字符（数字也算）数量最小，所以很明显不能用贪心。

再看看范围只有100，所以马上就能想到$O(N^3)$的区间dp。

考虑状态转移，当前节点t将l~r的区间分割成l~t两部分t+1~r

结合题目的性质就可以发现有两种状态的转移

1.f[l][r]=max(f[l][r], f[l][t] + f[t + 1][r])这个没什么好讲

2.尝试用l~t区间中的字母来覆盖整个区间。

判断是否能够覆盖其实不用kmp之类的复杂算法，直接暴力求一个a[l][r]，表示l~r区间内的字符不断循环重复最远能够到达的位置，然后看看是否能够刚好覆盖完（余数为0）。

最后要注意嵌套（括号中还有括号）的情况。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 110;

int n; char s[N];

int a[N][N], f[N][N], p[N][N], b[N];

void dfs(int l, int r) {
    if (l == r) { putchar(s[l]); return; }
    int t = p[l][r];
    if (f[l][r] == f[l][t] + f[t + 1][r]) {
        dfs(l, t), dfs(t + 1, r);
    }
    else {
        printf("%d", (r - l + 1) / (t - l + 1));
        putchar('(');
        dfs(l, t);
        putchar(')');
    }
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i < 10; i++) b[i] = 1;
    for (int i = 10; i < 100; i++) b[i] = 2;
    b[100] = 3;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++) {
            int now = l - 1;
            for (int i = r + 1; i <= n; i++) {
                now++; if (now == r + 1) now = l;
                if (s[now] != s[i]) {
                    a[l][r] = i - 1;
                    break;
                }
            }
            if (!a[l][r]) a[l][r] = n;
        }
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) f[i][i] = 1;
    for (int k = 1; k <= n; k++)
        for (int l = 1; l + k - 1 <= n; l++) {
            int r = l + k - 1;
            for (int t = l; t < r; t++) {
                if (f[l][t] + f[t + 1][r] < f[l][r])
                    f[l][r] = f[l][t] + f[t + 1][r], p[l][r] = t;
                if (a[l][t] >= r && (r - l + 1) % (t - l + 1) == 0) {
                    int sum = f[l][t] + 2 + b[(r - l + 1) / (t - l + 1)];
                    if (sum < f[l][r]) f[l][r] = sum, p[l][r] = t;
                }
            }
        }
    dfs(1, n);
    return 0;
}