洛谷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\)

有史以来做过最神奇的区间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;
}

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/lydsy1068%3Blg2470.html