给出一个字符串，把它分成 $k$ 块，块内可以任意排序，连续的相同字母算作一段，求最终字符串中的最小段数。
链接
UVA 11552
题解
这题目描述有毒，刚看完前半部分，这不是 SCOI 的压缩吗?再一看后面和前面没有任何关系…
$f[i][j]$ 表示前 $i$ 块，第 $i$ 块第 $j$ 位排最后的最小段数。
显然块内相同的字符肯定排在一起，$g[i]$ 表示第 $i$ 块内字符种数，转移如下：
$$f[i][j] = \begin{cases}\min_k\{ f[i - 1][k] + g[i] - 1\} & k \in \text{block}_i, (g[i] = 1 \text{ or }k \neq j)\\
\min_k\{ f[i - 1][k] + g[i]\} & \text{otherwise}\end{cases}$$
时间复杂度 $O(Tnk)$
代码
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
|
#include <bits/extc++.h>
namespace {
const int MAXN = 1000;
char s[MAXN + 1];
int f[MAXN + 1][MAXN + 1];
inline void solveCase() {
register int k, len, block;
std::cin >> k >> s;
len = strlen(s);
block = len / k;
for (register int i = 0; i < block; i++)
memset(f[i], 0x3f, sizeof(int) * k);
static std::bitset<127> vis;
for (register int i = 0, chunks; i < block; i++) {
chunks = 0, vis.reset();
for (register int j = i * k; j < (i + 1) * k; j++) vis.set(s[j]);
for (register int j = 'a'; j <= 'z'; j++) chunks += vis.test(j);
if (i == 0) {
for (register int j = 0; j < k; j++) f[i][j] = chunks;
continue;
}
for (register int end = i * k, j = 0; j < k; end++, j++) {
for (register int pre = (i - 1) * k, l = 0; l < k; pre++, l++) {
if (vis.test(s[pre]) && (chunks == 1 || s[pre] != s[end])) {
f[i][j] = std::min(f[i][j], f[i - 1][l] + chunks - 1);
} else {
f[i][j] = std::min(f[i][j], f[i - 1][l] + chunks);
}
}
}
}
std::cout << *std::min_element(f[len / k - 1], f[len / k - 1] + k) << '\n';
}
inline void solve() {
register int T;
for (std::cin >> T; T--;) solveCase();
}
}
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
solve();
return 0;
}
|
