class Solution {
public:
int minCost(vector<int>& nums, int k) {
}
};
2547. 拆分数组的最小代价
给你一个整数数组 nums 和一个整数 k 。
将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。
令 trimmed(subarray) 作为子数组的一个特征，其中所有仅出现一次的数字将会被移除。
trimmed([3,1,2,4,3,4]) = [3,4,3,4] 。子数组的 重要性 定义为 k + trimmed(subarray).length 。
[1,2,3,3,3,4,4] ，trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4] 。这个子数组的重要性就是 k + 5 。找出并返回拆分 nums 的所有可行方案中的最小代价。
子数组 是数组的一个连续 非空 元素序列。
示例 1：
输入：nums = [1,2,1,2,1,3,3], k = 2 输出：8 解释：将 nums 拆分成两个子数组：[1,2], [1,2,1,3,3] [1,2] 的重要性是 2 + (0) = 2 。 [1,2,1,3,3] 的重要性是 2 + (2 + 2) = 6 。 拆分的代价是 2 + 6 = 8 ，可以证明这是所有可行的拆分方案中的最小代价。
示例 2：
输入：nums = [1,2,1,2,1], k = 2 输出：6 解释：将 nums 拆分成两个子数组：[1,2], [1,2,1] 。 [1,2] 的重要性是 2 + (0) = 2 。 [1,2,1] 的重要性是 2 + (2) = 4 。 拆分的代价是 2 + 4 = 6 ，可以证明这是所有可行的拆分方案中的最小代价。
示例 3：
输入：nums = [1,2,1,2,1], k = 5 输出：10 解释：将 nums 拆分成一个子数组：[1,2,1,2,1]. [1,2,1,2,1] 的重要性是 5 + (3 + 2) = 10 。 拆分的代价是 10 ，可以证明这是所有可行的拆分方案中的最小代价。
提示：
1 <= nums.length <= 10000 <= nums[i] < nums.length1 <= k <= 109
原站题解
java 解法, 执行用时: 16 ms, 内存消耗: 41.3 MB, 提交时间: 2023-01-23 10:47:28
class Solution {
public int minCost(int[] nums, int k) {
int n = nums.length, ans = 0;
mn = new int[n * 4];
todo = new int[n * 4];
int[] last = new int[n], last2 = new int[n];
for (int i = 1; i <= n; ++i) {
int x = nums[i - 1];
update(1, 1, n, i, i, ans); // 相当于设置 f[i+1] 的值
update(1, 1, n, last[x] + 1, i, -1);
if (last[x] > 0) update(1, 1, n, last2[x] + 1, last[x], 1);
ans = k + query(1, 1, n, 1, i);
last2[x] = last[x];
last[x] = i;
}
return ans + n;
}
// Lazy 线段树模板（区间加，查询区间最小）
private int[] mn, todo;
private void do_(int o, int v) {
mn[o] += v;
todo[o] += v;
}
private void spread(int o) {
int v = todo[o];
if (v != 0) {
do_(o * 2, v);
do_(o * 2 + 1, v);
todo[o] = 0;
}
}
// 区间 [L,R] 内的数都加上 v o,l,r=1,1,n
private void update(int o, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
do_(o, v);
return;
}
spread(o);
int m = (l + r) / 2;
if (m >= L) update(o * 2, l, m, L, R, v);
if (m < R) update(o * 2 + 1, m + 1, r, L, R, v);
mn[o] = Math.min(mn[o * 2], mn[o * 2 + 1]);
}
// 查询区间 [L,R] 的最小值 o,l,r=1,1,n
private int query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R)
return mn[o];
spread(o);
int m = (l + r) / 2;
if (m >= R) return query(o * 2, l, m, L, R);
if (m < L) return query(o * 2 + 1, m + 1, r, L, R);
return Math.min(query(o * 2, l, m, L, R), query(o * 2 + 1, m + 1, r, L, R));
}
}
java 解法, 执行用时: 30 ms, 内存消耗: 40.8 MB, 提交时间: 2023-01-23 10:47:13
class Solution {
public int minCost(int[] nums, int k) {
int n = nums.length;
int[] f = new int[n + 1];
byte[] state = new byte[n];
for (int i = 0; i < n; ++i) {
Arrays.fill(state, (byte) 0);
int unique = 0, mn = Integer.MAX_VALUE;
for (int j = i; j >= 0; --j) {
int x = nums[j];
if (state[x] == 0) { // 首次出现
state[x] = 1;
++unique;
} else if (state[x] == 1) { // 不再唯一
state[x] = 2;
--unique;
}
mn = Math.min(mn, f[j] - unique);
}
f[i + 1] = k + mn;
}
return f[n] + n;
}
}
golang 解法, 执行用时: 24 ms, 内存消耗: 6.6 MB, 提交时间: 2023-01-23 10:46:45
func minCost(nums []int, k int) int {
n := len(nums)
f := make([]int, n+1)
for i := 0; i < n; i++ {
state, unique, mn := make([]int8, n), 0, math.MaxInt
for j := i; j >= 0; j-- {
x := nums[j]
if state[x] == 0 { // 首次出现
state[x] = 1
unique++
} else if state[x] == 1 { // 不再唯一
state[x] = 2
unique--
}
mn = min(mn, f[j]-unique)
}
f[i+1] = mn + k
}
return f[n] + n
}
func min(a, b int) int { if a > b { return b }; return a }
golang 解法, 执行用时: 16 ms, 内存消耗: 5.3 MB, 提交时间: 2023-01-23 10:46:22
// Lazy 线段树模板（区间加，查询区间最小）
type seg []struct{ l, r, min, todo int }
func (t seg) build(o, l, r int) {
t[o].l, t[o].r = l, r
if l == r {
return
}
m := (l + r) >> 1
t.build(o<<1, l, m)
t.build(o<<1|1, m+1, r)
}
func (t seg) do(o, v int) {
t[o].min += v
t[o].todo += v
}
func (t seg) spread(o int) {
if v := t[o].todo; v != 0 {
t.do(o<<1, v)
t.do(o<<1|1, v)
t[o].todo = 0
}
}
// 区间 [l,r] 内的数都加上 v o=1
func (t seg) update(o, l, r, v int) {
if l <= t[o].l && t[o].r <= r {
t.do(o, v)
return
}
t.spread(o)
m := (t[o].l + t[o].r) >> 1
if l <= m {
t.update(o<<1, l, r, v)
}
if m < r {
t.update(o<<1|1, l, r, v)
}
t[o].min = min(t[o<<1].min, t[o<<1|1].min)
}
// 查询区间 [l,r] 的最小值 o=1
func (t seg) query(o, l, r int) int {
if l <= t[o].l && t[o].r <= r {
return t[o].min
}
t.spread(o)
m := (t[o].l + t[o].r) >> 1
if r <= m {
return t.query(o<<1, l, r)
}
if l > m {
return t.query(o<<1|1, l, r)
}
return min(t.query(o<<1, l, r), t.query(o<<1|1, l, r))
}
func minCost(nums []int, k int) (ans int) {
n := len(nums)
last := make([]int, n)
last2 := make([]int, n)
t := make(seg, n*4)
t.build(1, 1, n)
for i, x := range nums {
i++ // 线段树区间从 1 开始
t.update(1, i, i, ans) // 相当于设置 f[i+1] 的值
t.update(1, last[x]+1, i, -1)
if last[x] > 0 {
t.update(1, last2[x]+1, last[x], 1)
}
ans = k + t.query(1, 1, i)
last2[x] = last[x]
last[x] = i
}
return ans + n
}
func min(a, b int) int { if a > b { return b }; return a }
python3 解法, 执行用时: 624 ms, 内存消耗: 18.6 MB, 提交时间: 2023-01-23 10:46:04
class Solution:
def minCost(self, nums: List[int], k: int) -> int:
# Lazy 线段树模板（区间加，查询区间最小）
n = len(nums)
mn = [0] * (4 * n)
todo = [0] * (4 * n)
def do(o: int, v: int) -> None:
mn[o] += v
todo[o] += v
def spread(o: int) -> None:
v = todo[o]
if v:
do(o * 2, v)
do(o * 2 + 1, v)
todo[o] = 0
# 区间 [L,R] 内的数都加上 v o,l,r=1,1,n
def update(o: int, l: int, r: int, L: int, R: int, v: int) -> None:
if L <= l and r <= R:
do(o, v)
return
spread(o)
m = (l + r) // 2
if m >= L: update(o * 2, l, m, L, R, v)
if m < R: update(o * 2 + 1, m + 1, r, L, R, v)
mn[o] = min(mn[o * 2], mn[o * 2 + 1])
# 查询区间 [L,R] 的最小值 o,l,r=1,1,n
def query(o: int, l: int, r: int, L: int, R: int) -> int:
if L <= l and r <= R:
return mn[o]
spread(o)
m = (l + r) // 2
if m >= R: return query(o * 2, l, m, L, R)
if m < L: return query(o * 2 + 1, m + 1, r, L, R)
return min(query(o * 2, l, m, L, R), query(o * 2 + 1, m + 1, r, L, R))
ans = 0
last = [0] * n
last2 = [0] * n
for i, x in enumerate(nums, 1):
update(1, 1, n, i, i, ans) # 相当于设置 f[i+1] 的值
update(1, 1, n, last[x] + 1, i, -1)
if last[x]: update(1, 1, n, last2[x] + 1, last[x], 1)
ans = k + query(1, 1, n, 1, i)
last2[x] = last[x]
last[x] = i
return ans + n
python3 解法, 执行用时: 2512 ms, 内存消耗: 15.2 MB, 提交时间: 2023-01-23 10:45:50
class Solution:
def minCost(self, nums: List[int], k: int) -> int:
n = len(nums)
f = [0] * (n + 1)
for i in range(n):
state, unique, mn = [0] * n, 0, inf
for j in range(i, -1, -1):
x = nums[j]
if state[x] == 0: # 首次出现
state[x] = 1
unique += 1
elif state[x] == 1: # 不再唯一
state[x] = 2
unique -= 1
mn = min(mn, f[j] - unique)
# if f[j]-unique < mn: mn = f[j]-unique # 手写 min 会快很多
f[i + 1] = k + mn
return f[n] + n