【每日一题】[CQOI2007]涂色PAINT

[CQOI2007]涂色PAINT

https://ac.nowcoder.com/acm/problem/19909

题目

题目描述：

假设你有一条长度为5的木版，初始时没有涂过任何颜色。

你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。

每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。

例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。用尽量少的涂色次数达到目标。

输入描述：

输入仅一行，包含一个长度为n的字符串，即涂色目标。
字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。

输出描述：

仅一行，包含一个数，即最少的涂色次数。

解析

1）知识点

看题目易得，这是一道dp的题目，但是dp数组是啥就是一个问题了。这道题其实是一个区间dp。

2）看题目

题目说，我们可以一笔画一条，最少要多少下画成现在要的这个亚子（表示可以覆盖）。

3）算法分析

首先，我们确定了这是dp：动态规划最重要的就是递推和dp数组的含义。
首先是dp数组的含义：
1. 这道题里面重要的是，对于这个木板，你最少画了多少下。
2. 然后这里我们就可以假设，某一个区间里面，最少要画多少下（这样算木板就是从头到尾）。
然后就是递推了：
1. 递推的时候我们可以分成三种情况。
2. 假如区间长度为1，说明就一个位置，一笔就可以了，就设置为1。
3. 否则，当左端点和右端点相等的时候，说明可以一笔从左到右。
  假设这里是dp[l][r]，就说明dp[l + 1][r]和dp[l][r - 1]也可以被一笔画到。
  那么也可以说dp[l][r]是由这两个延申过来的，所以dp[l][r]为他们间的较小值。
4. 但假如左右不相等呢，说明要从l画到r，肯定要有一个过渡用的点。
  因为两个不同的颜色要变换过去，肯定要过渡一次呀（这个时候过渡点可以是r前面的任何点，因为过渡点也可能被覆盖了）。
  那么这个时候，我们就循环判断一遍！

4）算法操作

首先说明我们的dp数组：

int dp[MAX][MAX];//dp[left][right] = 最小次数

然后要注意，因为两个点之间本来不知道多少次，要求最小值，我们就将其初始化为正无穷：
```
memset(dp, INF, sizeof dp);
```
接下来就是递推了：
前提，我们的双重循环第一层为len表示区间长度，第二层为l表示左端点（因为要先求出最短的，构建好了底层，才能进行dp计算）。
首先是长度为1的特判：
```
if (len == 1) dp[l][r] = 1;
```

然后是首尾相等的判断：

if (str[l] == str[r]) dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);

最后是首尾不相等时候的循环遍历：

else 
        for (int i = 1; i < r; i++)
                dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r]);

5）打代码

打代码嘞！
首先还是输入。
dp没什么好说的，就是开始递推就好了。
看我代码~

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//预处理

const int MAX = 1e3 + 7;
const int INF = 0x3f3f3f3f;
string str;
int dp[MAX][MAX];//dp[left][right] = 最小次数
//全局变量

int main() {
    IOS;
    cin >> str;
    //输入

    int len_str = str.length();
    str = ' ' + str;
    memset(dp, INF, sizeof dp);
    for (int len = 1; len <= len_str; len++)
        for (int l = 1; l + len - 1 <= len_str; l++) {
            int r = l + len - 1;
            if (len == 1) dp[l][r] = 1;
            else {
                if (str[l] == str[r]) dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
                else 
                    for (int i = 1; i < r; i++)
                        dp[l][r] = min(dp[l][r], dp[l][i] + dp[i + 1][r]);    
            }
        }
    //操作

    cout << dp[1][len_str] << endl;
    //输出
    return 0;
}
//函数体

每日一题文章被收录于专栏

憨憨的专栏