BZOJ1068【SCOI2007】压缩 <区间DP>

Problem

【SCOI2007】压缩

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

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

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

Input

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

Output

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

Sample Input

Input #1

aaaaaaa

Input #2

bcdcdcdcdxcdcdcdcd

Sample Output

Output #1

5

Output #2

12

HINT

样例解释
在第一个样例中，解为$\mathrm{aaaRa}$，在第二个例子中，解为$\mathrm{bMcdRRxMcdRR}$。
数据规模
$100\%$的数据满足$1\le n\le50$

标签：区间DP

Solution

每次压缩的是连续的一段，考虑区间$\mathrm{DP}$。

设$f[l][r]$表示压缩字符串$s$的字串$s[l..r]$的最短长度，其中压缩后的串串首自带一个$\mathrm{M}$于是就会有两种转移：

• $f[l][r]=\min_{i=l}^{r-1}(f[l][i]+f[i+1][r])$
• 若$s[l..mid]=s[mid+1..r]$，则$f[l][r] = \min(f[l][r],f[l][mid]+2)$

但这样是有锅的…压缩后串中间的$\mathrm{M}$会影响到后面的$\mathrm{R}$。
例如$\mathrm{orzwxhakakorzwxhakak}$，显然$\mathrm{orzwxhMakR}$为一种压缩，但其复制一遍形成的$\mathrm{MorzwxhMakRR}$表示的不是原串。这是因为中间的$\mathrm{M}$会使后面的$\mathrm{R}$少复制一截。

于是我们调整状态定义，定义$f[l][r][0]$表示压缩后除了串首不再含有任何一个$\mathrm{M}$，$f[l][r][1]$表示压缩后除了串首还含有其他$\mathrm{M}$，这样前者是可以整体复制的，而后者不行。
那么首先有边界条件$f[i][i][1]=2\;(i\in[1,n])$。
转移有三种：

• $f[l][r][0]=\min_{i=l}^{r-1}(f[l][i][0]+r-i)$，表示直接把后缀接上去
• $f[l][r][0]=\min(f[l][r][0],f[l][mid][0]+1)$，其中$s[l..mid]=s[mid+1..r]$，表示把前一半复制一遍
• $f[l][r][1]=\min_{i=l}^{r-1}(\min(f[l][i][0],f[l][i][1])+\min(f[i+1][r][0],f[i+1][r][1]))$，表示分成两半随便拼，只不过拼了以后不能复制，因为中间有$\mathrm{M}$

直接记忆化即可，注意第三种情况要判左右边界。

Code

#include <bits/stdc++.h>
#define MAX_N 50
#define INF 0x3f3f3f3f
#define mid ((l+r)>>1)
using namespace std;
int n, f[MAX_N+5][MAX_N+5][2];    char s[MAX_N+5];
int DP(int l, int r, bool x) {
    int &ret = f[l][r][x];
    if (ret^INF) return ret;
    if (l == r && !x) return ret = 2;
    if (x) {
        for (int i = l; i < r; i++) {
            ret = min(ret, DP(l, i, 0)+DP(i+1, r, 0));
            if (l < i) ret = min(ret, DP(l, i, 0)+DP(i+1, r, 1));
            if (i+1 < r) ret = min(ret, DP(l, i, 1)+DP(i+1, r, 0));
            if (l < i && i+1 < r) ret = min(ret, DP(l, i, 1)+DP(i+1, r, 1));
        }
    } else {
        for (int i = l; i < r; i++)
            ret = min(ret, DP(l, i, 0)+r-i);
        bool flag = (r-l)%2 == 1;
        for (int i = l, j = mid+1; i <= mid; i++, j++)
            if (s[i]^s[j]) flag = false;
        if (flag) ret = min(ret, DP(l, mid, 0)+1);
    }
    return ret;
}
int main() {
    scanf("%s", s+1), n = (int)strlen(s+1);
    memset(f, INF, sizeof f), DP(1, n, 0), DP(1, n, 1);
    return printf("%d", min(f[1][n][0], f[1][n][1])-1), 0;
}