3181. 执行操作可获得的最大总奖励 II

来源第 401 场周赛 Q4难度困难分数2688

题目描述

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并标记下标 i。

以整数形式返回执行最优操作能够获得的最大总奖励。

示例 1：

输入：rewardValues = [1,1,3,3]

输出：4

解释：

依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]

输出：11

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

提示：

1 <= rewardValues.length <= 5 * 10⁴
1 <= rewardValues[i] <= 5 * 10⁴

解法

方法一：动态规划 + 位运算

思考

规则与 I 相同而值域更大，布尔数组 DP 的 \(O(nM)\) 不能通过。

仍是「低 \(v\) 位左移 \(v\) 再或回 \(f\)」，位图一次处理一个字。

排序去重后 \(f=1\)，对每个 \(v\) 做 \(f\mathrel{|}=(f\&((1\ll v)-1))\ll v\)，返回 \(f.bit\_length()-1\)。

我们定义 \(f[i][j]\) 表示用前 \(i\) 个奖励值，能否得到总奖励 \(j\)。初始时 \(f[0][0] = \textit{True}\)，其余值均为 \(\textit{False}\)。

我们考虑第 \(i\) 个奖励值 \(v\)，如果我们不选择它，那么 \(f[i][j] = f[i - 1][j]\)；如果我们选择它，那么 \(f[i][j] = f[i - 1][j - v]\)，其中 \(0 \leq j - v \lt v\)。即状态转移方程为：

\[ f[i][j] = f[i - 1][j] \vee f[i - 1][j - v] \]

最终答案为 \(\max\{j \mid f[n][j] = \textit{True}\}\)。

由于 \(f[i][j]\) 只与 \(f[i - 1][j]\) 和 \(f[i - 1][j - v]\) 有关，我们可以优化掉第一维，只使用一个一维数组进行状态转移。另外，由于本题数据范围较大，我们需要使用位运算来优化状态转移的效率。

我们定义一个二进制数 \(f\) 保存当前的状态，其中 \(f\) 的第 \(i\) 位为 \(1\) 表示当前总奖励为 \(i\) 是可达的。

观察上述状态转移方程 \(f[j] = f[j] \vee f[j - v]\)，这相当于取 \(f\) 的低 \(v\) 位，再左移 \(v\) 位，然后与原来的 \(f\) 进行或运算。

那么答案为 \(f\) 的最高位的位置。

时间复杂度 \(O(n \times M / w)\)，空间复杂度 \(O(n + M / w)\)。其中 \(n\) 是数组 rewardValues 的长度，而 \(M\) 是数组 rewardValues 中的最大值的两倍。整数 \(w = 32\) 或 \(64\)。

Python3JavaC++GoTypeScript

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        nums = sorted(set(rewardValues))
        f = 1
        for v in nums:
            f |= (f & ((1 << v) - 1)) << v
        return f.bit_length() - 1

import java.math.BigInteger;

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        int[] nums = Arrays.stream(rewardValues).distinct().sorted().toArray();
        BigInteger f = BigInteger.ONE;
        for (int v : nums) {
            BigInteger mask = BigInteger.ONE.shiftLeft(v).subtract(BigInteger.ONE);
            BigInteger shifted = f.and(mask).shiftLeft(v);
            f = f.or(shifted);
        }
        return f.bitLength() - 1;
    }
}

class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        rewardValues.erase(unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
        bitset<100000> f{1};
        for (int v : rewardValues) {
            int shift = f.size() - v;
            f |= f << shift >> (shift - v);
        }
        for (int i = rewardValues.back() * 2 - 1;; i--) {
            if (f.test(i)) {
                return i;
            }
        }
    }
};

func maxTotalReward(rewardValues []int) int {
    slices.Sort(rewardValues)
    rewardValues = slices.Compact(rewardValues)
    one := big.NewInt(1)
    f := big.NewInt(1)
    p := new(big.Int)
    for _, v := range rewardValues {
        mask := p.Sub(p.Lsh(one, uint(v)), one)
        f.Or(f, p.Lsh(p.And(f, mask), uint(v)))
    }
    return f.BitLen() - 1
}

function maxTotalReward(rewardValues: number[]): number {
    rewardValues.sort((a, b) => a - b);
    rewardValues = [...new Set(rewardValues)];
    let f = 1n;
    for (const x of rewardValues) {
        const mask = (1n << BigInt(x)) - 1n;
        f = f | ((f & mask) << BigInt(x));
    }
    return f.toString(2).length - 1;
}

3181. 执行操作可获得的最大总奖励 II

题目描述

解法

方法一：动态规划 + 位运算

评论