「Codeforces 1120C」Compress String

Description

给定一个长度为 $n$ 的字符串 $s$，现在有一个打字机，每次你可以花费 $a$ 的代价打出一个字符，或者花费 $b$ 的代价打出一个 已经打出的字符串 的子串，求打出 $s$ 的最小代价。$(1 \leq n,a,b \leq 5 \times 10^3)$

Source

[Luogu]CF1120C

[Codeforces]1120C

Solution

很容易想到 $O(n^3)$ 的 DP 。

我们用 $f_i$ 表示打完前 $i$ 个字符所需要的最小代价，状态转移方程为

$$\large { f_i = \min \left( f_{i - 1} + a,\min \{ f_{i - k}\} + b \right) }$$

考虑第 $i$ 个字符是怎么打出来的。

可以先打出前 $i - 1$ 个字符，然后花费 $a$ 的代价打出第 $i$ 个字符。

设子串的末尾为第 $j$ 个字符，子串的长度为 $k$，则可以先打出前 $i - k$ 个字符，再花费 $b$ 的代价打出 $k$ 个字符。前提是 $s_{i-k + 1, i}$ 与 $s_{j - k + 1, j}$ 相等，可以用 $\rm hash$ 判断。

最后取上述两种情况的最小值即可。

如何优化？

不难发现，$f$ 数组的值其实是单调不减的。

换句话说，方程中 $k$ 的值要尽可能大。

而 $k$ 的最大值其实是 $s_{1,i}$ 与 $s_{1,j}$ 的 最长公共后缀 长度。

于是我们可以省去对 $k$ 的枚举，同样的状态，新转移方程为

$$\large { f_i = \min \left( f_{i - 1} + a, \min \{f_{\max\left(i - LPS_{i,j}, j\right)} \} + b \right) }$$

其中 $LPS_{i,j}$ 表示 $s_{1, i}$ 与 $s_{1,j}$ 的最长公共后缀长度。之所以要与 $j$ 取 $\max$，是因为已经假设子串末尾为第 $j$ 个字符，$i - LPS_{i,j}$ 的值肯定不能比 $j$ 小，否则就等于取了 还没打出来的字符串 的子串。

图示：

$\rm LPS(最长公共后缀)$ 可以用 $O(n^2)$ DP 预处理，考虑第 $s_i$ 和 $s_j$ 是否相等即可。

$$\large { LPS_{i,j} = \left\{\begin{matrix} LPS_{i - 1,j - 1} + 1 & (s_i = s_j)\\[2ex] 0 & (s_i \neq s_j) \end{matrix}\right. }$$

当然这道题也可以用 $\rm SA(后缀数组)$ 维护 DP，只不过写起来麻烦一点。

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

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 5e3;
int n, a, b, f[MAXN + 5], lps[MAXN + 5][MAXN + 5];
char s[MAXN + 5];

int main() {
    read(n), read(a), read(b);
    scanf("%s", s + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            lps[i][j] = s[i] == s[j] ? lps[i - 1][j - 1] + 1 : 0;//预处理最长公共后缀
    memset(f, 0x3f, sizeof (f));
    f[0] = 0;//初始状态：不打字花费的代价为 0 
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + a;
        for (int j = 1; j < i; ++j)
            f[i] = min(f[i], f[max(i - lps[i][j], j)] + b);//转移 
    }
    write(f[n]);
    putchar('\n');
    return 0;
}