3181. 执行操作可获得的最大总奖励 II
题目描述
给你一个整数数组 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 * 104
1 <= rewardValues[i] <= 5 * 104
解法
方法一:动态规划 + 位运算
我们定义 $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$。
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|