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;}
};