[Codeforces1120C] Compress String

题目链接: https://codeforces.com/contest/1120/problem/C

题目大意

你有一个长度为 \(n\) 个字符串 \(s\)
请你把 \(s\) 拆成若干个字符串 \(s=t_1t_2\cdots t_k\)
对于第 \(i\) 个串,若 \(t_i\)\(t_1t_2\cdots t_{i-1}\) 的字符串,你需要付出 \(b\) 的代价,否则 \(t_i\) 长度必须为 \(1\),你需要付出 \(a\) 的代价。求最小代价。
\(n \le 5000\),字符集大小 \(26\)

解法

\(dp_i\) 表示前 \(i\) 个字符的最小划分,在求出 \(dp_i\) 后用 \(kmp\) 找最长在前面出现过的从 \(i+1\) 开始的串,更新所有 \(dp_j\)

代码

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
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 5010;
const int inf = 0x3f3f3f3f;

int n, a, b, fail[maxn], dp[maxn];
char s[maxn];

int main() {
scanf("%d%d%d", &n, &a, &b);
scanf("%s", s+1);
fail[0] = -1;
for (int i = 1; i <= n; i++) {
int cur = fail[i-1];
while (cur != -1) {
if (s[cur+1] == s[i]) {
fail[i] = cur+1;
break;
}
cur = fail[cur];
}
}
for (int i = 1; i <= n; i++) dp[i] = inf;
for (int i = 0; i <= n; i++) {
fail[0] = -1;
for (int j = 1; i+j <= n; j++) {
int cur = fail[j-1];
fail[j] = 0;
while (cur != -1) {
if (s[i+cur+1] == s[i+j]) {
fail[j] = cur+1;
break;
}
cur = fail[cur];
}
}
int p = 0, mx = 0;
for (int j = 1; j <= i; j++) {
while (p != -1) {
if (s[i+p+1] == s[j]) {
++ p;
break;
}
if (p) p = fail[p];
else break;
}
if (p > mx) mx = p;
}
for (int j = 1; j <= mx; j++) {
dp[i+j] = min(dp[i+j], dp[i]+b);
}
dp[i+1] = min(dp[i+1], dp[i]+a);
}
printf("%d\n", dp[n]);
return 0;
}