题目描述

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。

压缩后的字符串除了小写字母外还可以 (但不必) 包含大写字母 R 与 M，其中 M 标记重复串的开始，R 重复从上一个 M (如果当前位置左边没有 M，则从串的开始算起) 开始的解压结果 (称为缓冲串)。

$\texttt{bcdcdcdcd}$ 可以压缩为 $\texttt{bMcdRR}$，下面是解压缩的过程：

另一个例子是 $\texttt{abcabcdabcabcdxyxyz}$ 可以被压缩为 $\texttt{abcRdRMxyRz}$。

输入格式

输入仅一行，包含待压缩字符串，仅包含小写字母，长度为 $n$ ($n \leq 50$)。

输出格式

输出一行一个整数，即压缩后字符串的最短长度。

题解

跟这道题类似，考虑使用区间 DP。

由于 $M$ 的默认开头性有点麻烦，因此方便起见，我们约定所有段落均以 $\texttt{M}$ 开头 (不管是否压缩，如题目描述中的字符串被压缩成 $\texttt{MbMcdRR}$)。

记 $f_{i, j}$ 表示子串 $s[i..j]$ 能被压缩到的最短长度 (包括开头的 $\texttt{M}$)，那么答案就是 $f_{1, n} - 1$ 且有边界 $f_{i, i} = 2$。

不过，在相同的串拼接时候的转移中，你会发现，这个缓冲串检测的 $\texttt{M}$ 只会像右移动，比如说你想压缩 $ABBABB$ 之类的 ($A, B$ 是子串)，那么不能提前把两个 $B$ 压缩起来 ($\texttt{M}B\texttt{R}$)，这样 $ABB$ 就无法压缩了，因此只能压缩成 $\texttt{M}ABB\texttt{R}$ 或另找他法。

那么，$s[i..j-1]$ 能否和 $s[j..k-1]$ ($k = 2j - i$) 合并取决于 $s[i..j]$ 的压缩串中除了开头的 $\texttt{M}$ 外是否有其它的 $\texttt{M}$。

于是，重新记 $f_{i, j}$ 表示子串 $s[i..j]$ 的压缩串中，除了开头的 $\texttt{M}$ 外，没有其它的 $\texttt{M}$，这样的压缩串的最短长度，$g_{i, j}$ 表示压缩串除开头的 $\texttt{M}$ 外，还有其它的 $\texttt{M}$，这样的最短长度。那么答案就是 $\min \left\{ f_{1, n}, g_{1, n} \right\} - 1$，且有边界 $f_{i, i} = 2$。

考虑 $f_{i, j}$ 的转移。第一种情况，即两串合并，那么要满足 $k = \dfrac {i + j + 1} 2$ 为整数，且 $s[i..k-1] = s[k..j]$，那么由于 $s[i..k]$ 的压缩串中只有开头的 $\texttt{M}$，那么就有 $$ f_{i, j} \downarrow f_{i, k-1} + 1 $$

第二种情况，即平凡地添加字符。那么对 $\forall k \in [i, j)$，有 $$ f_{i, j} \downarrow f_{i, k} + j - k $$

然后是 $g_{i, j}$ 的转移。这个随便转移即可，找到两边的拼起来就可以了。对 $\forall k \in [i, j)$，转移方程为 $$ g_{i, j} \downarrow \min \left\{ f_{i, k}, g_{i, k} \right\} + \min \left\{ f_{k+1, j}, g_{k+1, j} \right\} $$

时间复杂度为 $O(n^3)$。

代码

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

char s[N];
int n, d, i, j, k, l, hd;
int f[N][N], g[N][N];
// f[i][j]: compress (i, j) with only a 'M' at first
// g[i][j]: compress (i, j) with over one 'M'

void down(int &x, const int y) {x > y ? x = y : 0;}

int main(){
    scanf("%s", s + 1); n = strlen(s + 1);
    memset(f, 63, sizeof f);
    memset(g, 63, sizeof g);
    for(i = 1; i <= n; ++i) f[i][i] = 2;
    for(d = 1; d < n; ++d)
        for(hd = d >> 1, i = 1; i <= n - d; ++i){
            if(j = i + d, d & 1){ // can split
                for(l = j - hd, k = 0; k <= hd; ++k) if(s[i + k] != s[l + k]) break;
                if(k > hd) down(f[i][j], f[i][l - 1] + 1); // [i, l) = [l, j)
            }
            for(k = i; k < j; ++k){
                down(f[i][j], f[i][k] + j - k);
                down(g[i][j], min(f[i][k], g[i][k]) + min(f[k + 1][j], g[k + 1][j]));
            }
        }
    printf("%d\n", min(f[1][n], g[1][n]) - 1);
    return 0;
}

坑

要注意本题的压缩特征，从而采用两个数组相互 DP。当然，也可以记 $f_{i, j}$ 的那个长度不包括 $\texttt{M}$，最终答案不 $- 1$，也可以 DP 出来。