class Solution {
public:
int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
}
};
100259. 划分数组得到最小的值之和
给你两个数组 nums 和 andValues，长度分别为 n 和 m。
数组的 值 等于该数组的 最后一个 元素。
你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组 [li, ri]，子数组元素的按位AND运算结果等于 andValues[i]，换句话说，对所有的 1 <= i <= m，nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] ，其中 & 表示按位AND运算符。
返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 -1 。
示例 1：
输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]
输出： 12
解释：
唯一可能的划分方法为：
[1,4] 因为 1 & 4 == 0[3] 因为单元素子数组的按位 AND 结果就是该元素本身[3] 因为单元素子数组的按位 AND 结果就是该元素本身[2] 因为单元素子数组的按位 AND 结果就是该元素本身这些子数组的值之和为 4 + 3 + 3 + 2 = 12
示例 2：
输入： nums = [2,3,5,7,7,7,5], andValues = [0,7,5]
输出： 17
解释：
划分 nums 的三种方式为：
[[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 + 7 + 5 = 17[[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19[[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19子数组值之和的最小可能值为 17
示例 3：
输入： nums = [1,2,3,4], andValues = [2]
输出： -1
解释：
整个数组 nums 的按位 AND 结果为 0。由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2，因此返回 -1。
提示：
1 <= n == nums.length <= 1041 <= m == andValues.length <= min(n, 10)1 <= nums[i] < 1050 <= andValues[j] < 105原站题解
golang 解法, 执行用时: 26 ms, 内存消耗: 6.5 MB, 提交时间: 2024-08-16 09:21:03
func minimumValueSum(nums, andValues []int) int {
const inf = math.MaxInt / 2
n := len(nums)
f := make([]int, n+1)
for i := 1; i <= n; i++ {
f[i] = inf
}
newF := make([]int, n+1)
for _, target := range andValues {
nums := slices.Clone(nums)
left, right := 0, 0
q := []int{} // 单调队列，保存 f 的下标
qi := 0 // 单调队列目前处理到 f[qi]
newF[0] = inf
for i, x := range nums {
for j := i - 1; j >= 0 && nums[j]&x != nums[j]; j-- {
nums[j] &= x
}
for left <= i && nums[left] < target {
left++
}
for right <= i && nums[right] <= target {
right++
}
// 上面这段的目的是求出子数组右端点为 i 时，子数组左端点的最小值和最大值+1
// 下面是单调队列的滑窗过程
if left < right {
// 单调队列：右边入
for ; qi < right; qi++ {
for len(q) > 0 && f[qi] <= f[q[len(q)-1]] {
q = q[:len(q)-1]
}
q = append(q, qi)
}
// 单调队列：左边出
for q[0] < left {
q = q[1:]
}
// 单调队列：计算答案
newF[i+1] = f[q[0]] + x // 队首就是最小值
} else {
newF[i+1] = inf
}
}
f, newF = newF, f
}
if f[n] < inf {
return f[n]
}
return -1
}
python3 解法, 执行用时: 680 ms, 内存消耗: 18.3 MB, 提交时间: 2024-08-16 09:20:17
class Solution:
def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
n = len(nums)
f = [0] + [inf] * n
new_f = [0] * (n + 1)
for target in andValues:
a = nums.copy() # 也可以写 nums[:]
left = right = 0 # 子数组右端点为 i 时，子数组左端点的最小值和最大值+1
q = deque() # 单调队列，保存 f 的下标
qi = 0 # 单调队列目前处理到 f[qi]
new_f[0] = inf
for i, x in enumerate(a):
for j in range(i - 1, -1, -1):
if a[j] & x == a[j]:
break
a[j] &= x
while left <= i and a[left] < target:
left += 1
while right <= i and a[right] <= target:
right += 1
# 上面这段的目的是求出子数组右端点为 i 时，子数组左端点的最小值和最大值+1
# 下面是单调队列的滑窗过程
if left < right:
# 单调队列：右边入
while qi < right:
while q and f[qi] <= f[q[-1]]:
q.pop()
q.append(qi)
qi += 1
# 单调队列：左边出
while q[0] < left:
q.popleft()
# 单调队列：计算答案
new_f[i + 1] = f[q[0]] + x # 队首就是最小值
else:
new_f[i + 1] = inf
f, new_f = new_f, f
return f[n] if f[n] < inf else -1
golang 解法, 执行用时: 478 ms, 内存消耗: 121.7 MB, 提交时间: 2024-04-15 14:30:58
func minimumValueSum(nums, andValues []int) int {
n, m := len(nums), len(andValues)
type args struct{ i, j, and int }
memo := map[args]int{}
var dfs func(int, int, int) int
dfs = func(i, j, and int) int {
if m-j > n-i { // 剩余元素不足
return math.MaxInt / 2
}
if j == m { // 分了 m 段
if i == n {
return 0
}
return math.MaxInt / 2
}
and &= nums[i]
if and < andValues[j] { // 剪枝：无法等于 andValues[j]
return math.MaxInt / 2
}
p := args{i, j, and}
if res, ok := memo[p]; ok {
return res
}
res := dfs(i+1, j, and) // 不划分
if and == andValues[j] { // 划分，nums[i] 是这一段的最后一个数
res = min(res, dfs(i+1, j+1, -1)+nums[i])
}
memo[p] = res
return res
}
ans := dfs(0, 0, -1)
if ans == math.MaxInt/2 {
return -1
}
return ans
}
cpp 解法, 执行用时: 919 ms, 内存消耗: 248.3 MB, 提交时间: 2024-04-15 14:29:46
class Solution {
unordered_map<long long, int> memo;
int dfs(int i, int j, int and_, vector<int>& nums, vector<int>& andValues) {
int n = nums.size(), m = andValues.size();
if (m - j > n - i) { // 剩余元素不足
return INT_MAX / 2;
}
if (j == m) { // 分了 m 段
return i == n ? 0 : INT_MAX / 2;
}
and_ &= nums[i];
if (and_ < andValues[j]) { // 剪枝：无法等于 andValues[j]
return INT_MAX / 2;
}
long long mask = (long long) i << 36 | (long long) j << 32 | and_; // 三个状态压缩成一个 long long
if (memo.contains(mask)) {
return memo[mask];
}
int res = dfs(i + 1, j, and_, nums, andValues); // 不划分
if (and_ == andValues[j]) { // 划分，nums[i] 是这一段的最后一个数
res = min(res, dfs(i + 1, j + 1, -1, nums, andValues) + nums[i]);
}
return memo[mask] = res;
}
public:
int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
int ans = dfs(0, 0, -1, nums, andValues);
return ans < INT_MAX / 2 ? ans : -1;
}
};
java 解法, 执行用时: 201 ms, 内存消耗: 131.4 MB, 提交时间: 2024-04-15 14:29:18
class Solution {
public int minimumValueSum(int[] nums, int[] andValues) {
Map<Long, Integer> memo = new HashMap<>();
int ans = dfs(0, 0, -1, nums, andValues, memo);
return ans < Integer.MAX_VALUE / 2 ? ans : -1;
}
private int dfs(int i, int j, int and, int[] nums, int[] andValues, Map<Long, Integer> memo) {
int n = nums.length;
int m = andValues.length;
if (m - j > n - i) { // 剩余元素不足
return Integer.MAX_VALUE / 2;
}
if (j == m) { // 分了 m 段
return i == n ? 0 : Integer.MAX_VALUE / 2;
}
and &= nums[i];
if (and < andValues[j]) { // 剪枝：无法等于 andValues[j]
return Integer.MAX_VALUE / 2;
}
long mask = (long) i << 36 | (long) j << 32 | and; // 三个状态压缩成一个 long
if (memo.containsKey(mask)) {
return memo.get(mask);
}
int res = dfs(i + 1, j, and, nums, andValues, memo); // 不划分
if (and == andValues[j]) { // 划分，nums[i] 是这一段的最后一个数
res = Math.min(res, dfs(i + 1, j + 1, -1, nums, andValues, memo) + nums[i]);
}
memo.put(mask, res);
return res;
}
}
python3 解法, 执行用时: 1328 ms, 内存消耗: 419.8 MB, 提交时间: 2024-04-15 14:29:01
# 记忆化搜索+选/不选
class Solution:
def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
n, m = len(nums), len(andValues)
@cache
def dfs(i: int, j: int, and_: int) -> int:
if m - j > n - i: # 剩余元素不足
return inf
if j == m: # 分了 m 段
return 0 if i == n else inf
and_ &= nums[i]
if and_ < andValues[j]: # 剪枝：无法等于 andValues[j]
return inf
res = dfs(i + 1, j, and_) # 不划分
if and_ == andValues[j]: # 划分，nums[i] 是这一段的最后一个数
res = min(res, dfs(i + 1, j + 1, -1) + nums[i])
return res
ans = dfs(0, 0, -1)
return ans if ans < inf else -1