自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 21:37:17，当前版本为作者最后更新于2021-09-11 10:33:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

比较套路的区间 DP。

设 $f_{i,j}$ 为区间 $[l,r]$ 最短可以压缩到的长度，则转移方程为：

1. $f_{i,j}=\min\limits_{k=i}^{j-1}{f_{i,k}+f_{k+1,j}}$

这个比较好理解，就是将 $[i,k]$ 和 $[k+1,j]$ 两段已经压缩到最短的字符串直接拼在一起。

2. $f_{i,j}=\min\limits_{k=1}^{j-i}f_{i,i+k-1}+2+\operatorname{digit}(\frac{j-i+1}{k})$（$k$ 是 $j-i+1$ 的因数且 $[i,i+k-1]$ 是 $[i,j]$ 的一个周期）

这个也不是很难想，因为是周期，所以可以压缩，长度即为 $[i,i+k-1]$ 可以压缩到的最短长度加上两个括号再加上 $\frac{j-i+1}{k}$ 的位数（$\frac{j-i+1}{k}$ 表示这个周期连续出现的次数）。

由于题目还要求输出方案，所以用 $ans_{i,j}$ 记录 $[i,j]$ 最短可以压缩到的字符串，当发现有更优决策时更新 $ans_{i,j}$ 即可。

边界条件为：$f_{i,i}=1$，$ans_{i,i}=s_i$。

附赠三倍经验：P4302，UVA1630

代码

#include <bits/stdc++.h>
using namespace std;

int n, f[110][110];
string s, ans[110][110];

int digit(int x) {
    int res = 0;
    while (x) {
        ++res;
        x /= 10;
    }
    return res;
}

string int2str(int x) {
    stringstream ss;
    ss << x;
    return ss.str();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    n = s.size();
    s = ' ' + s;
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            ans[i][j] = "";
        }
    }
    for (int i = 1; i <= n; ++i) {
        f[i][i] = 1;
        ans[i][i] = s[i];
    }
    for (int p = 2; p <= n; ++p) {
        for (int i = 1, j = p; j <= n; ++i, ++j) {
            for (int k = i; k < j; ++k) {
                if (f[i][j] > f[i][k] + f[k + 1][j]) {
                    f[i][j] = f[i][k] + f[k + 1][j];
                    ans[i][j] = ans[i][k] + ans[k + 1][j];
                }
            }
            for (int k = 1; k < p; ++k) {
                if (p % k) {
                    continue;
                }
                bool flag = 1;
                for (int l = k; l + i <= j; ++l) {
                    if (s[l + i] != s[l % k + i]) {
                        flag = 0;
                        break;
                    }
                }
                if (flag) {
                    if (f[i][j] > f[i][i + k - 1] + 2 + digit(p / k)) {
                        f[i][j] = f[i][i + k - 1] + 2 + digit(p / k);
                        ans[i][j] = int2str(p / k) + '(' + ans[i][i + k - 1] + ')';
                    }
                }
            }
        }
    }
    cout << ans[1][n] << endl;
    return 0;
}