洛谷P2470 [SCOI2007]压缩题解

题目链接：P2470 [SCOI2007]压缩

题意：

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

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

已经解压的部分解压结果缓冲串

$\mathtt{b}$ $\mathtt{b}$ $\mathtt{b}$

$\mathtt{bM}$ $\mathtt{b}$ $\varnothing$

$\mathtt{bMc}$ $\mathtt{bc}$ $\mathtt{c}$

$\mathtt{bMcd}$ $\mathtt{bcd}$ $\mathtt{cd}$

$\mathtt{bMcdR}$ $\mathtt{bcdcd}$ $\mathtt{cdcd}$

$\mathtt{bMcdRR}$ $\mathtt{bcdcdcdcd}$ $\mathtt{cdcdcdcd}$

输入格式:

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

输出格式:

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

数据范围：

$100\%$ 的数据满足：$1\le n\le 50$

已经解压的部分	解压结果	缓冲串
$\mathtt{b}$	$\mathtt{b}$	$\mathtt{b}$
$\mathtt{bM}$	$\mathtt{b}$	$\varnothing$
$\mathtt{bMc}$	$\mathtt{bc}$	$\mathtt{c}$
$\mathtt{bMcd}$	$\mathtt{bcd}$	$\mathtt{cd}$
$\mathtt{bMcdR}$	$\mathtt{bcdcd}$	$\mathtt{cdcd}$
$\mathtt{bMcdRR}$	$\mathtt{bcdcdcdcd}$	$\mathtt{cdcdcdcd}$

有史以来做过最神奇的区间dp

由于 $\tt{M}$ 的设计~~极其鬼畜~~，因此套路地设每个考虑的段均以 $\tt{M}$ 开头（~~可以无视这句话~~）

首先设 $f_{i,j}$ 表示 $[i,j]$ 能被压缩到的最短长度（包括开头的 $\tt{M}$ ）

则答案为 $f_{1,n} - 1$ ，且 $f_{i,i} = 2$

不过，在相同串拼接时的转移中，这个缓冲串检测的 $\tt{M}$ 只会向右移

例如我们想压缩 $ABBABB$ （$A,B$ 为某个子串）

那就不能提前压缩 $BB$ 为 $\mathtt{M}B\mathtt{R}$ ，这样后面更优的 $\mathtt{M}ABB\mathtt{R}$ 就无法使用了。

这一点应该很容易发现，但是怎么处理呢？

注意到此时的dp状态无法记录这样的情况

因为我们不知道当前处理的这一段中间有没有出现过 $\mathtt{M}$

~~嗨害嘿~~，这不都说出来了吗？

于是我们重新设 $f_{i,j}$ 表示 $[i,j]$ 能被压缩到的最短长度（包括开头的 $\tt{M}$ ），且除了开头的 $\mathtt{M}$ ，中间没有其他的 $\mathtt{M}$

相应地，设 $g_{i,j}$ 表示中间出现过别的 $\mathtt{M}$

考虑 $f_{i,j}$ 的转移。下文中用 $a\downarrow b+c$ 表示 $a\leftarrow \min\{a,b+c\}$。

第一种情况，两串合并，则要求 $k=\frac{i+j+1}{2} \in \mathbb{Z}$ ，且 $s[i\dots k-1]=s[k\dots j]$ ，则

$f_{i,j}\downarrow f_{i,k-1}+1$

第二种情况，直接添加字符

$f_{i,j} \downarrow f_{i,k} + j - k$

然后考虑 $g_{i,j}$ 的转移，没啥好考虑的，直接拼上

$g_{i,j} \downarrow \min\{f_{i,k},~g_{i,k}\} + \min\{f_{k+1,j},~g_{k+1,j}\}$

~~感觉做完了好像也没啥特别的~~

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

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(70))

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

char s[N];
int n;
int f[N][N],g[N][N];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s+1); n = strlen(s+1);
    memset(f,0x3f,sizeof(f)); memset(g,0x3f,sizeof(g));
    for(int i=1; i<=n; i++) f[i][i] = 2;
    for(int d=1,j,k,l; d<n; d++)
        for(int 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);
            }
            for(int 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]));
            }
        }
    cout << min(f[1][n], g[1][n]) - 1 << '\n';
    return 0;
}