UVA1630 串折叠 Folding 题解

简单区间DP。因为最后输出的是一个字符串，所以设string类型的二维数组 $f_{i,j}$ 表示字符串 $s_{i, j}$ 折叠后形成的最短字符串。（当然也可以让 $f$ 定义为整型，代表长度，同时再设一个二维数组存字符串）。由于 $f$ 是字符型的，所以DP时 $f$ 的最大值要赋成一个很长的字符串：

std::string f[MAXN + 3][MAXN + 3], INF(200, '@');
//INF为最大值

接着就很好DP了，对于每个字符串 $s_{i,j}$ ，如果不折叠，就是把它分成两个部分，那两个部分再继续处理。如果要折叠，就枚举折叠长度 $len$，再判断是否可以折叠，则转移方程：

$f_{i,j}= \begin{cases} min\{f_{i,k}+f_{k+1,j}\}\\ min\{len+(+f_{i,i+len-1}+)\} \end{cases}$

注意方程中的 $+$ 表示字符串拼接，$len$ 必须要是区间长度的约数。$min$ 函数是比较长度的，所以要重定义一下。

初始化：$f_{i,i} = s_i$

那么代码也就很轻松了：

std::string mn(std::string x, std::string y) {
    return x.size() < y.size() ? x : y;
}
bool judge(std::string s, int len) {//判断是否可折叠
    for (int i = 0; i < s.size(); i++)
        if (s[i] != s[i % len])
            return 0;
    return 1;
}
std::string ntos(int x) {//将数字转为字符，便于拼接
    std::string s = "";
    do {
        s = (char)(x % 10 + '0') + s, x /= 10;
    } while (x);
    return s;
}
for (int i = 0; i < MAXN; i++)//MAXN是最大长度
    for (int j = 0; j < MAXN; j++)
        f[i][j].clear();
for (int i = 0; i < s.size(); i++)
    f[i][i] = s[i];
for (int i = s.size() - 2; i >= 0; i--)
    for (int j = i + 1; j < s.size(); j++) {
        f[i][j] = INF;
        for (int k = i; k < j; k++)
            f[i][j] = mn(f[i][j], f[i][k] + f[k + 1][j]);
        for (int len = 1; len <= j - i + 1; len++)
        //这里其实不用枚举这么多，但是这么做也行
            if (!((j - i + 1) % len) && judge(s.substr(i, j - i + 1), len))
                f[i][j] = mn(f[i][j], ntos((j - i + 1) / len) + '(' + f[i][i + len - 1] + ')');
    }

时间复杂度：$O(n^3)$ ，可优化到 $O(n^2\sqrt n)$ 。

完整代码不贴了。