P4170 [CQOI2007] 涂色 题解

· · 题解

Getting Start

管理撤了没有证明的题解咳咳，试着抢一发。

现在想起来这题是当初 dp 入门的噩梦（）。

题意简述

原题链接：https://www.luogu.com.cn/problem/P4170

把宽为 1 的白板刷成指定颜色最少要刷几次，每次刷的长度和位置任意，新颜色会覆盖在旧颜色上。

解题思路

看 tag 知区间 dp（doge）

刷子每次对一个区间的颜色造成影响，可以倒着考虑。

由小到大考虑每个区间，长为 1 的区间显然只要刷 1 次。长度大于 1 的区间，就假设已经处理好了所有长度更小的区间的答案（dp 和记忆化搜索的精髓：从子问题最优解逐步推到全局最优解）。

对于该区间两端的颜色来说，如果这两个颜色相同，完全可以最先刷上这个颜色，从一端直接刷到该区间另一端，把两端之间的别的颜色放后面再刷，覆盖在区间上。

设 dp_{l,r} 表示当区间左端点为 l，右端点为 r 时，最少要刷多少次，该种情况即有转移：

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

如果该区间两端的颜色不同，没法一刷子搞定。枚举断点 k，把整个区间分成左右两部分，答案即为两部分花费之和的最小值：

dp_{l,r} = \min_{k=l}^{r-1}{dp_{l,k} + dp_{k+1,r}}

考虑正确性。证明不太严谨但可以意会。

两端颜色相同时比较显然，一刷到底和两端各刷一次相比，节省了一刷子的花费。

因为除了一刷到底也没有别的节省花费的方法了，两端颜色不同时，肯定至少要刷两次，同时希望区间里别的颜色花费尽量小，就枚举断点找最小花费和：还是从子问题最优推到全局最优。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int maxn = 55;

string board;
int dp[maxn][maxn];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> board;
    int n = board.size();

    memset(dp, 0x3f, sizeof dp);
    for(int i = 0; i < n; i ++)
        dp[i][i] = 1; //这个初始化其实就是区间长为 1 的情况

    for(int len = 2; len <= n; len ++) //所以直接从 2 开始了
        for(int l = 0; l + len - 1 < n; l ++){
            int r = l + len - 1;
            if(board[l] == board[r])
                dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
            else
                for(int k = l; k < r; k ++)
                    dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
        }

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

    return 0;
}

Ending

完结撒花。如果有解释的不到位的地方欢迎评论提出。

希望所有刚接触区间 dp 的 OIer 们都能吃透这道题。