题目描述

给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小
写字母外还可以(但不必)包含大写字母R与M,其中M标记重复串的开始,R重复从上一个M(如果当前位置左边没
有M,则从串的开始算起)开始的解压结果(称为缓冲串)。 bcdcdcdcd可以压缩为bMcdRR,下面是解压缩的过程
另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

输入

输入仅一行,包含待压缩字符串,仅包含小写字母,长度为n。

输出

输出仅一行,即压缩后字符串的最短长度。

样例输入

bcdcdcdcdxcdcdcdcd

样例输出

12

提示

在第一个例子中,解为 aaaRa,在第二个例子中,解为 bMcdRRxMcdRR。
100% 的数据满足:1 <= n <= 50

题解

很好的一道区间 DP 的题,我自己肯定是做不出来的,看了眼题解勉强写出来了。
n <= 50 显然是立方的 DP,我们要做的就是把重复串压缩。

按照区间 DP 的传统套路我们应该用 fi 表示 区间 [l, r] 压缩后的最小长度。
但是对于类似于样例的一个字串 cdcdcdcd 能否压缩取决于前面有没有 M,这启示我们需要开第三维。

我们用 fi[k] 表示区间 [l, r] 压缩后的最小长度,k = 0 或 1。初值就是 fi[k] = 1

当 k = 0 时,我们假设这个区间前面有一个紧挨着它的 M,且要保证区间内没有 M,当这个区间长度是偶数且从中间分开两个字串是一样的,我们认为这个串可以压缩,如果不能压缩,这个区间的字串可能可以压缩,那就枚举下中间点 k,开始区间 DP 的老套路拆成两个区间 [l, k], [k+1, r],转移方程就是这样。

f[i][j][0] = min(f[i][(l+r)/2][0], f[i][k] + j - k)

当 k = 1 时,不做任何限制,对于一个区间,我们枚举放 M 的位置。

f[i][j][1] = min(f[i][j][0], f[i][k][1] + 1 + f[k+1][j])

还是不懂可以看下代码

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100;
int n;
char s[N];
int f[N][N][2];
bool check(int l, int r) {
    if((r - l + 1) % 2 != 0) return false;
    int p1 = l, p2 = (l + r + 1) / 2;
    int cnt = (r - l + 1) / 2 - 1;
    for(int i=0; i<=cnt; i++)
        if(s[p1+i] != s[p2+i]) return false;
    return true;
}
int main() {
    scanf("%s", s+1);
    n = strlen(s+1);
    memset(f, 0x3f, sizeof f);
    for(int i=1; i<=n; i++) f[i][i][0] = f[i][i][1] = 1;
    for(int i=n; i>=1; i--) {
        for(int j=i+1; j<=n; j++) {
            if(check(i, j))
                f[i][j][0] = min(f[i][j][0], f[i][(i+j)/2][0] + 1);
            for(int k=i; k<=j; k++)
                f[i][j][0] = min(f[i][j][0], f[i][k][0] + j - k);
        }
    }

    for(int i=n; i>=1; i--) {
        for(int j=i+1; j<=n; j++) {
            f[i][j][1] = min(f[i][j][1], f[i][j][0]);
            for(int k=i; k<=j; k++) {
                f[i][j][1] = min(f[i][j][1], f[i][k][1] + f[k+1][j][1] + 1);
            }
        }
    }
    printf("%d\n", f[1][n][1]);
    return 0;
}