#P4469. 第1题-单元标注
-
1000ms
Tried: 12
Accepted: 5
Difficulty: 7
所属公司 :
京东
时间 :2025年11月15日
-
算法标签>动态规划
第1题-单元标注
解题思路
题意整理:
- 有一个长度为
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]。
转移:
-
不考虑和右端点相同的合并,先把
dp[l][r]=dp[l][r−1]+1[l, r-1]弄好,再单独给r位置涂一遍: -
尝试“合并涂色”:
如果存在某个
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,其中Bi表示第i个单元的目标标签。
每次标注操作可以选择一个连续的区间[L,R],将该区间内所有单元的标签统一设为某个值x。小明想知道要完成目标标注最少需要多少次操作?
输入描述
第一行包含一个正整数N,表示存储单元的数量
第二行包含N个正整数,依次表示日标标签序列B(Bi为第i个单元的目标标签)。
N≤400,1≤Bi≤N
输出描述
一行,一个正整数,表不最少需要的标注操作次数
样例1
输入
8
4 4 1 1 1 4 4 4
输出
2
说明
先将全范围标 4,再覆盖中间区域标为1,仅需两次操作