Processing math: 100%

「Codeforces 1120C」Compress String

Description

给定一个长度为 n 的字符串 s,现在有一个打字机,每次你可以花费 a 的代价打出一个字符,或者花费 b 的代价打出一个 已经打出的字符串 的子串,求打出 s 的最小代价。(1n,a,b5×103)

Source

[Luogu]CF1120C

[Codeforces]1120C

Solution

很容易想到 O(n3)DP

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

fi=min(fi1+a,min{fik}+b)

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

可以先打出前 i1 个字符,然后花费 a 的代价打出第 i 个字符。

设子串的末尾为第 j 个字符,子串的长度为 k,则可以先打出前 ik 个字符,再花费 b 的代价打出 k 个字符。前提是 sik+1,isjk+1,j 相等,可以用 hash 判断。

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

如何优化?

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

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

k 的最大值其实是 s1,is1,j最长公共后缀 长度。

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

fi=min(fi1+a,min{fmax(iLPSi,j,j)}+b)

其中 LPSi,j 表示 s1,is1,j 的最长公共后缀长度。之所以要与 jmax,是因为已经假设子串末尾为第 j 个字符,iLPSi,j 的值肯定不能比 j 小,否则就等于取了 还没打出来的字符串 的子串。

图示:

EaEn0K.png

LPS() 可以用 O(n2) DP 预处理,考虑第 sisj 是否相等即可。

LPSi,j={LPSi1,j1+1(si=sj)0(sisj)

当然这道题也可以用 SA() 维护 DP,只不过写起来麻烦一点。

总时间复杂度为 O(n2)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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;
}

本文标题:「Codeforces 1120C」Compress String

文章作者:Heartlessly

发布时间:2019年05月04日 - 07:52:24

最后更新:2019年10月13日 - 18:26:23

原始链接:https://heartlessly.github.io/problems/codeforces-1120c/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

Gitalking ...

0%