0%

[CQOI2007] 涂色

题目

题目链接

题目大意:给出长度为 $n$ 的目标字符串,问最少几次能将空字符串涂成目标字符串,每次可以修改连续的一段。$1 \le n \le 50$。

思路

很明显是区间 DP。

设 $f(i, j)$ 表示将 $i$ 到 $j$ 涂成目标的最少花费,显然 $f(i, i) = 1$,最终答案为 $f(1, n)$。

考虑转移,如果 $a_i = a_j$,那么只需要第一次涂的时候顺便涂一下就行,有 $f(i, j) = \min(f(i + 1, j), f(i, j - 1))$。

如果 $a_i \neq a_j$,就需要设置断点 $k$,显然 $f(i, j) = \min(f(i, k) + f(k + 1, 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

int f[60][60];
int n;
char a[60];

int main() {
scanf("%s", a + 1);
n = strlen(a + 1);
for (int i = 1; i <= n; ++i) f[i][i] = 1;
for (int l = 2; l <= n; ++l) {
for (int i = 1; i + l - 1 <= n; ++i) {
int j = i + l - 1;
f[i][j] = 0x3f3f3f3f;
if (a[i] == a[j]) {
f[i][j] = std::min(f[i + 1][j], f[i][j - 1]);
} else {
for (int k = i; k < j; ++k) {
f[i][j] = std::min(f[i][j], f[i][k] + f[k + 1][j]);
}
}
}
}
printf("%d\n", f[1][n]);
return 0;
}