[CQOI2007] 涂色

题意

给出一个目标颜色串。初始木板是空白的，每次可以把一段连续区间涂成同一种颜色，后涂会覆盖前涂。

要求用最少的涂色次数得到目标字符串。

思路

最直接的做法是暴力递归，枚举最左字符怎么处理。

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

static string s;

int dfs(int l, int r) {
    if (l > r) {
        return 0;
    }
    if (l == r) {
        return 1;
    }

    int best = dfs(l + 1, r) + 1;

    // 暴力枚举 s[l] 想和后面哪个相同字符共用一次涂色。
    for (int k = l + 1; k <= r; ++k) {
        if (s[k] != s[l]) {
            continue;
        }
        int left = dfs(l + 1, k - 1);
        int right = dfs(k, r);
        best = min(best, left + right);
    }

    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;
    cout << dfs(0, (int)s.size() - 1) << '\n';
    return 0;
}

brute.cpp 会尝试两类方案：

把最左字符单独作为一次新的涂色
如果后面有相同字符，就尝试和它共用一次涂色

这个思路是对的，但不记忆化会重复计算大量相同子串。

于是设 dp[l][r] 表示把目标子串 s[l..r] 涂出来的最少次数。

最朴素的一种转移是：

dp[l][r] = dp[l+1][r] + 1

表示把 s[l] 单独开一笔，然后剩下的区间自己处理。

如果后面某个位置 k 满足 s[k] == s[l]，那么 s[l] 可以和 s[k] 共用一次涂色，不必额外多开一笔。此时可以转移为：

dp[l][r] = min(dp[l][r], dp[l+1][k-1] + dp[k][r])

这张表展示几个典型状态的含义：

状态	表示什么
`dp[2][2]`	单个字符，最少只要 `1` 次
`dp[2][4]`	把子串 `s[2..4]` 涂出来的最少次数
`dp[0][n-1]`	整个目标串的最少涂色次数，也就是最终答案

DP 公式

设 $dp_{l,r}$ 表示涂出子串 $s[l..r]$ 的最少次数。单独涂 $s_l$ 时：

dp_{l,r}=dp_{l+1,r}+1

如果存在 $k$ 满足 $l<k\leqslant r$ 且 $s_k=s_l$ ，则 $s_l$ 可以和 $s_k$ 共用一次涂色：

dp_{l,r}=\min(dp_{l,r},\ dp_{l+1,k-1}+dp_{k,r})

边界为 $dp_{i,i}=1$ ，最终答案为：

dp_{0,n-1}

读这张表时，关键是理解“相同字符可以共用一次涂色”依赖于覆盖操作。正因为后涂可以覆盖前涂，我们才能先粗涂一层，再把中间部分修正回来，从而减少总次数。

公式解释：先把最左字符单独涂是一种保底方案。若后面有相同字符，它们可以共用一次涂色，于是最左字符不需要单独开一笔，转移就拆成中间区间和右侧区间。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

static int dp[55][55];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = (int)s.size();

    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }

    // dp[l][r] 表示把目标子串 s[l..r] 涂出来的最少次数。
    for (int len = 2; len <= n; ++len) {
        for (int l = 0; l + len - 1 < n; ++l) {
            int r = l + len - 1;
            dp[l][r] = dp[l + 1][r] + 1;
            for (int k = l + 1; k <= r; ++k) {
                if (s[k] != s[l]) {
                    continue;
                }
                int left = (k == l + 1 ? 0 : dp[l + 1][k - 1]);
                dp[l][r] = min(dp[l][r], left + dp[k][r]);
            }
        }
    }

    cout << dp[0][n - 1] << '\n';
    return 0;
}

复杂度

区间 DP 需要枚举区间长度、左端点和位置 k，所以时间复杂度是 $O(n^3)$ ，空间复杂度是 $O(n^2)$ 。

总结

这题的核心不是直接模拟每一笔怎么涂，而是抓住“相同字符能共用一次涂色”这个覆盖性质。把它转成区间 DP 后，状态和转移都很自然。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析