解题思路

题意整理：

• 有一个长度为 N 的数组，初始每个位置都是“未标注”。
• 目标是把第 i 个位置标成给定的值 B[i]。
• 一次操作可以选择一个连续区间 [L, R]，把这个区间内所有位置的标签统一改成同一个值 x（可以任意选择，且可以覆盖之前的标注）。
• 问：完成目标数组 B 至少需要多少次操作。

这个问题本质上和经典的 “Strange Printer / 区间打印” 问题是同一个模型： 打印机初始是空白，每次可以把一个区间统一打印成某个颜色，并允许覆盖。

1. 预处理：压缩相邻相同元素

如果目标数组里有一段连续相同的值，比如 4 4 4，从“空白”状态变成它，无论如何需要把这一整段涂成 4，中间再分割没有任何好处。

因此可以先把数组按“相邻去重”压缩一下，例如：

• 原数组：4 4 1 1 1 4 4 4
• 压缩后：4 1 4

压缩后长度记为 M (M ≤ N)，只在这个新数组上做 DP 即可。

2. 区间 DP（算法：区间动态规划）

设压缩后的数组为 a[0 … M-1]。

定义 dp[l][r]： 从“全部未标注”开始，将下标区间 [l, r] 内变成目标 a[l…r] 所需要的最少操作次数。

边界：

• 单个元素：dp[i][i] = 1 只需要一次把这一位涂成 a[i]。

转移：

1. 不考虑和右端点相同的合并，先把 [l, r-1] 弄好，再单独给 r 位置涂一遍：

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

2. 尝试“合并涂色”：

   如果存在某个 k ( l ≤ k < r )，满足 a[k] == a[r]， 那么我们可以在涂 [l, k] 的某次操作中，顺便把位置 r 一并涂上同样的值， 这时只需要额外把中间的 [k+1, r-1] 按要求涂好即可。

   对应转移：

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

   若 k+1 > r-1（中间没有元素）则中间区间代价为 0。

最终答案为 dp[0][M-1]。

这种写法等价于“枚举右端点，再尝试和左边某个同色位置一起打印”，典型区间 DP。

复杂度分析

• 压缩数组：O(N)。
• DP 状态数：O(M^2)，M ≤ N。
• 对每个区间 [l, r] 枚举中间分割点 k：总体 O(M^3)。

因此总时间复杂度：O(N^3)，在 N ≤ 400 时完全可行。 空间复杂度：O(N^2) 用于存储 dp 数组。

代码实现

Python

import sys

# 计算最少操作次数的函数
def min_operations(arr):
    # 相邻去重压缩
    compressed = []
    for x in arr:
        if not compressed or compressed[-1] != x:
            compressed.append(x)

    # dp[l][r] 表示把区间 [l, r] 涂成目标的最少操作次数
    dp = [[0] * m for _ in range(m)]

    # 区间长度为 1 的情况
    for i in range(m):
        dp[i][i] = 1

    # 按区间长度枚举
    for length in range(2, m + 1):
        for l in range(0, m - length + 1):
            r = l + length - 1
            # 先假设单独给 r 位置涂一次
            dp[l][r] = dp[l][r - 1] + 1

            # 尝试和前面同色位置合并
            for k in range(l, r):
                if compressed[k] == compressed[r]:
                    # 中间区间 [k+1, r-1] 可能为空
                    if k + 1 <= r - 1:
                        val = dp[l][k] + dp[k + 1][r - 1]
                    else:
                        val = dp[l][k]
                    if val < dp[l][r]:
                        dp[l][r] = val

    return dp[0][m - 1]


def main():
    data = list(map(int, sys.stdin.read().split()))
    if not data:
        return
    n = data[0]
    arr = data[1:1 + n]
    ans = min_operations(arr)
    print(ans)


if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {

    // 计算最少操作次数的函数
    public static int minOperations(int[] arr, int n) {
        // 相邻去重压缩
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = arr[i];
            if (list.isEmpty() || list.get(list.size() - 1) != x) {
                list.add(x);
            }
        }

        int m = list.size();

        int[][] dp = new int[m][m];

        // 区间长度为 1 的情况
        for (int i = 0; i < m; i++) {
            dp[i][i] = 1;
        }

        // 按区间长度枚举
        for (int len = 2; len <= m; len++) {
            for (int l = 0; l + len - 1 < m; l++) {
                int r = l + len - 1;
                // 先假设单独给 r 位置涂一次
                dp[l][r] = dp[l][r - 1] + 1;

                // 尝试和前面同色位置合并
                for (int k = l; k < r; k++) {
                    if (list.get(k).intValue() == list.get(r).intValue()) {
                        int val;
                        if (k + 1 <= r - 1) {
                            val = dp[l][k] + dp[k + 1][r - 1];
                        } else {
                            val = dp[l][k];
                        }
                        if (val < dp[l][r]) {
                            dp[l][r] = val;
                        }
                    }
                }
            }
        }

        return dp[0][m - 1];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextInt()) {
            return;
        }
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int ans = minOperations(arr, n);
        System.out.println(ans);
    }
}

C++

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

// 计算最少操作次数的函数
int minOperations(const vector<int> &arr) {
    // 相邻去重压缩
    vector<int> b;
    for (size_t i = 0; i < arr.size(); ++i) {
        if (b.empty() || b.back() != arr[i]) {
            b.push_back(arr[i]);
        }
    }
    int m = (int)b.size();

    // dp[l][r] 表示将区间 [l, r] 涂成目标的最少操作次数
    static int dp[405][405];
    // 清零（实际上下面会全部覆盖，这里只是安全起见）
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < m; ++j)
            dp[i][j] = 0;

    // 区间长度为 1 的情况
    for (int i = 0; i < m; ++i) {
        dp[i][i] = 1;
    }

    // 按区间长度枚举
    for (int len = 2; len <= m; ++len) {
        for (int l = 0; l + len - 1 < m; ++l) {
            int r = l + len - 1;
            // 先假设单独给 r 位置涂一次
            dp[l][r] = dp[l][r - 1] + 1;

            // 尝试和前面同色位置合并
            for (int k = l; k < r; ++k) {
                if (b[k] == b[r]) {
                    int val;
                    if (k + 1 <= r - 1) {
                        val = dp[l][k] + dp[k + 1][r - 1];
                    } else {
                        val = dp[l][k];
                    }
                    if (val < dp[l][r]) {
                        dp[l][r] = val;
                    }
                }
            }
        }
    }

    return dp[0][m - 1];
}

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    int ans = minOperations(arr);
    cout << ans << "\n";

    return 0;
}

题目内容

某数据中心有一个包含N个连续存储单元的数组，初始时所有单元的标签均为“未标注”。数据管理员小明需要将这些单元标注为目标字列$8$，其中$B_i$表示第$i$个单元的目标标签。

每次标注操作可以选择一个连续的区间$[L,R]$，将该区间内所有单元的标签统一设为某个值$x$。小明想知道要完成目标标注最少需要多少次操作?

输入描述

第一行包含一个正整数$N$，表示存储单元的数量

第二行包含$N$个正整数，依次表示日标标签序列$B$($B_i$为第$i$个单元的目标标签)。

$N≤400，1≤B_i≤N$

输出描述

一行，一个正整数，表不最少需要的标注操作次数

样例1

输入

8
4 4 1 1 1 4 4 4

输出

2

说明

先将全范围标 4，再覆盖中间区域标为1，仅需两次操作