摘要
Title: 3181. 执行操作可获得的最大总奖励 II
Categories: 01背包、位运算
Powered by:NEFU AB-IN
Link
3181. 执行操作可获得的最大总奖励 II
题意
给你一个整数数组 rewardValues，长度为 n，代表奖励的值。
最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：
从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。
思路
https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/solutions/2805413/bitset-you-hua-0-1-bei-bao-by-endlessche-m1xn/
https://leetcode.cn/problems/maximum-total-reward-using-operations-i/solutions/2805418/di-tui-bitset-you-hua-by-tsreaper-c535/
定义 dp[i][j] 表示能否从前 i 个数中得到总奖励 j，由或运算进行转化
正常dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def maxTotalReward(self, rewardValues: List[int]) -> int:
rewardValues.sort()
rewardValues = [0] + rewardValues
n = len(rewardValues) - 1
m = rewardValues[-1] * 2
dp = Arr.array2d(False, n + 1, m + 1, )
dp[0][0] = True
for i in range(1, n + 1):
for j in range(m):
v = rewardValues[i]
dp[i][j] = dp[i - 1][j] or (dp[i - 1][j - v] and v <= j < 2 * v)
for j in range(m - 1, -1, -1):
if dp[n][j]:
return j
return 0
|
但可以注意到优化：
- 没必要每次都把j从0到m枚一遍（因为不满足j∈[v,2v)的dp[i][j]一定等于dp[i-1][j]），可以直接先复制dp[i-1]行
- 类似的删除第一个维度，从后往前遍历
得到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def maxTotalReward(self, rewardValues: List[int]) -> int:
rewardValues.sort()
rewardValues = [0] + rewardValues
n = len(rewardValues) - 1
m = rewardValues[-1] * 2
dp = Arr.array(False, m + 1, )
dp[0] = True
for i in range(1, n + 1):
v = rewardValues[i]
for j in range(2 * v - 1, v - 1, -1):
dp[j] = dp[j] or dp[j - v]
for j in range(m - 1, -1, -1):
if dp[j]:
return j
return 0
|
但如果是这样，还是空间复杂度不够，可以采取状态压缩
- 因为只有v, 2v这个区间的在变，所以我们需要让这个区间的数 或 上一个状态的 0, v
- 首先创建掩码，将 f 的低v位通过与运算取出来
- 左移v位，最后或即可
代码
1
2
3
4
5
6
7
| def maxTotalReward(self, rewardValues: List[int]) -> int:
rewardValues.sort()
f = 1
for v in rewardValues:
mask = (1 << v) - 1
f |= (f & mask) << v
return f.bit_length() - 1
|