3180. 执行操作可获得的最大总奖励 题解
来源于jager大佬的解释
假如数组中最大的元素为k，而最优解中最大的元素为x，那么使用k替换x肯定符合要求，即k肯定大于所选的其他的元素的和，满足题目的要求。由于使用k替换x之后得到了一个更优的解，因此假设错误，从而证明最大的元素k一定在最优解中，否则不是最优解。
根据以上我们可以证明数组一定包含最后一个元素，假设其值为k，则之前的累加和最大为k-1，则整个累加和最大范围为2k-1
我们可以先对数组排序，然后生成一个二维dp表，行为每个数，列为累加和范围
```js
rewardValues = rewardValues.sort((a, b) => a - b)
const dp = new Array(rewardValues.length).fill(0)
.map(() => new Array(rewardValues * 2).fill(0))
```
先考虑边界，首先累加和为0任何数字都可以满足
第一行只有累加和为0以及累加和要求为第一个数字两种状态为真
其他行则存在选和不选两种状态，如果不选则判断从0...i-1是否存在j的累加和
假设数字为k
如果选，则判断0...-1是否存在的累加和
由于存在累加和不得大于该数字，则如果选的话，最大的边界范围不得大于这个边界
而需要的累加和如果小于该数字，则无法选这个数字，只有不选一种选择
可得选数字的范围为[k,2*k)
```js
var maxTotalReward = function (rewardValues) {
rewardValues = rewardValues.sort((a, b) => a - b)
const dp = new Array(rewardValues.length).fill(0)
.map(() => new Array(rewardValues * 2).fill(0))
dp = true
dp] = true
for (let index = 1; index < dp.length; index++) {
for (let indey = 0; indey < dp.length; indey++) {
dp = dp
if (indey >= rewardValues && indey < 2 * rewardValues) {
dp = dp || dp]
}
}
}
for (let index = dp.length - 1; index >= 0; index--) {
if (dp == true) {
return index
}
}
return 0
};
```
最后我们直接判断最后一个数字，倒叙查找是否存在第一个为真返回即可
## 基础优化
我们可以看到每一行都转移了该上一行的数据，然后判断是否属于该数字的范围，如果属于则判断是否为真，并设置上
那就可以进行状态压缩到一行
需要注意的是遍历k数字的范围需要从大到小，如果从小到大容易出现本行的状态引用问题
```js
var maxTotalReward = function (rewardValues) {
rewardValues = rewardValues.sort((a, b) => a - b)
const dp = new Array(rewardValues * 2).fill(false)
dp = true
dp] = true
for (let index = 1; index < rewardValues.length; index++) {
const rewardValue = rewardValues
for (let indey = 2 * rewardValues - 1; indey >= rewardValues; indey--) {
dp = dp || dp
}
}
for (let index = dp.length - 1; index >= 0; index--) {
if (dp == true) {
return index
}
}
return 0
};
```
至此就实现了dp的推测和状态压缩 这题周赛第四题没错出，第三题简化版倒是做出了，没想到是 bitset db ，第一次遇到，以后遇到这种题用 python 最方便
```python
f = 1
for x in sorted(set(a)):
m = f & ( (1 << x) - 1)
f |= m << x
return f.bit_length() - 1
```
页:
[1]