本文主要是介绍3117. 划分数组得到最小的值之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
3117. 划分数组得到最小的值之和
题目链接:3117. 划分数组得到最小的值之和
代码如下:
//参考链接:https://leetcode.cn/problems/minimum-sum-of-values-by-dividing-array/solutions/2739258/ji-yi-hua-sou-suo-jian-ji-xie-fa-by-endl-728z
class Solution
{
public:int minimumValueSum(vector<int>& nums, vector<int>& andValues) {const int INF = INT_MAX / 2; // 除 2 防止下面 + nums[i] 溢出int n = nums.size(), m = andValues.size();unordered_map<long long, int> memo;auto dfs = [&](auto&& dfs, int i, int j, int and_) -> int{if (n - i < m - j) // 剩余元素不足{ return INF;}if (j == m)// 分了 m 段{ return i == n ? 0 : INF;}and_ &= nums[i];// 三个参数压缩成一个 long longlong long mask = (long long) i << 36 | (long long) j << 32 | and_;if (memo.contains(mask)) { // 之前计算过return memo[mask];}int res = dfs(dfs, i + 1, j, and_); // 不划分if (and_ == andValues[j]) // 划分,nums[i] 是这一段的最后一个数{ res = min(res, dfs(dfs, i + 1, j + 1, -1) + nums[i]);}return memo[mask] = res; // 记忆化};int res = dfs(dfs, 0, 0, -1);return res < INF ? res : -1;}
};
这篇关于3117. 划分数组得到最小的值之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!