洛谷 P4170 分析（别看）

科技起源

2026-07-06 13:52:07

发布于：河北

0阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：尽量少的涂色次数

1.2 题目背景、允许、禁止与限制

背景：有一个空的序列
允许：选择其中连续的一段，将其中所有项目颜色都涂成一样的。
禁止：
限制：后涂的颜色将会覆盖先涂的颜色。最后要将空白序列涂成题目给出字符串序列的样子

1.3 题目数据范围与猜测

$1 \le n \le 50 \longrightarrow O(n^4)$

1.4 一句话概括题意

有一个空序列，每次可以选择其中连续的一段，将其中所有项目颜色都涂成一样的。后涂的颜色将会覆盖先涂的颜色。最后要将空白序列涂成题目给出字符串序列的样子。求最少操作次数。

2 题目破题推导

注：以下六种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 以终为始、以始为终

2.4 数学

2.5 分情况考虑

如果对于 $[i,j-1]$ 这个区间， $j$ 号点的颜色 $=i$ 号点的颜色，那么刚第一次染 $[i,j-1]$ 的时候，我们可以额外染一下 $j$ ，这一定是最优方案
其他情况，最优方案一定是枚举 $[i,j]$ 中的所有断点 $k$ ，然后 $[i,k]+[k+1,j]$ 的所有可能最小值。

2.6 手动推导

2.7 边界测试

3 模型匹配

先提取关键词：时刻求取当前最小值、区间
是 $\huge{区间动态规划}$

4 具体方案

4.1 动态规划定义（重点）

首先，先建立 dp 数组
设置 ${dp_i}_j$ 表示把区间 $[i,j]$ 染成题目给定字符串所需最小染色次数

4.2 初始化

求最小值，所以dp数组每一项都设为大值
但是染一格只需要一次，因此对于每个 $i (1 \le i \le n)$ ，都要将 ${dp_i}_i$ 设置为 $1$

4.3 状态转移方程

我们的定义清晰了，合法方案也清晰了，因此直接就是（懒得打latex数学公式了）

for (int len = 2;len <= n;len++){
    for (int l = 1;l + len - 1 <= n;l++){
        int r = l + len - 1;
        if (s[l] == s[r]){
            dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
        }
        for (int k = l;k <= r - 1;k++){
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
        }
    }
}

4.4 答案求取

${dp_1}_n$

5 最终代码（禁止抄袭，仅用于参考）

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

int n;
const int N = 55;
string s;
int dp[N][N];

int main(){

    cin >> s;
    s = " " + s;
    n = s.size() - 1;
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1;i <= n;i++){
        dp[i][i] = 1;
    }
    for (int len = 2;len <= n;len++){
        for (int l = 1;l + len - 1 <= n;l++){
            int r = l + len - 1;
            if (s[l] == s[r]){
                dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
            }
            for (int k = l;k <= r - 1;k++){
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
            }
        }
    }
    cout << dp[1][n];
    
    return 0;
}