P2400 题解

· · 题解

思路

比较套路的区间 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] 两段已经压缩到最短的字符串直接拼在一起。

这个也不是很难想，因为是周期，所以可以压缩，长度即为 [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;
}