3180. 执行操作可获得的最大总奖励 题解

李恒道

来源于jager大佬的解释

假如数组中最大的元素为k，而最优解中最大的元素为x，那么使用k替换x肯定符合要求，即k肯定大于所选的其他的元素的和，满足题目的要求。由于使用k替换x之后得到了一个更优的解，因此假设错误，从而证明最大的元素k一定在最优解中，否则不是最优解。

根据以上我们可以证明数组一定包含最后一个元素，假设其值为k，则之前的累加和最大为k-1，则整个累加和最大范围为2k-1

我们可以先对数组排序，然后生成一个二维dp表，行为每个数，列为累加和范围

    rewardValues = rewardValues.sort((a, b) => a - b)
    const dp = new Array(rewardValues.length).fill(0)
        .map(() => new Array(rewardValues[rewardValues.length - 1] * 2).fill(0))

先考虑边界，首先累加和为0任何数字都可以满足
第一行只有累加和为0以及累加和要求为第一个数字两种状态为真
其他行则存在选和不选两种状态，如果不选则判断从0...i-1是否存在j的累加和
假设数字为k
如果选，则判断0...-1是否存在[j-k]的累加和
由于存在累加和不得大于该数字，则如果选的话，最大的边界范围不得大于[k*2]这个边界
而需要的累加和如果小于该数字，则无法选这个数字，只有不选一种选择
可得选数字的范围为[k,2*k)

var maxTotalReward = function (rewardValues) {
    rewardValues = rewardValues.sort((a, b) => a - b)
    const dp = new Array(rewardValues.length).fill(0)
        .map(() => new Array(rewardValues[rewardValues.length - 1] * 2).fill(0))
    dp[0][0] = true
    dp[0][rewardValues[0]] = true
    for (let index = 1; index < dp.length; index++) {
        for (let indey = 0; indey < dp[0].length; indey++) {
            dp[index][indey] = dp[index - 1][indey]
            if (indey >= rewardValues[index] && indey < 2 * rewardValues[index]) {
                dp[index][indey] = dp[index][indey] || dp[index - 1][indey - rewardValues[index]]
            }
        }
    }
    for (let index = dp[0].length - 1; index >= 0; index--) {
        if (dp[dp.length - 1][index] == true) {
            return index
        }
    }
    return 0
};

最后我们直接判断最后一个数字，倒叙查找是否存在第一个为真返回即可


基础优化

我们可以看到每一行都转移了该上一行的数据，然后判断是否属于该数字的范围，如果属于则判断是否为真，并设置上
那就可以进行状态压缩到一行
需要注意的是遍历k数字的范围需要从大到小，如果从小到大容易出现本行的状态引用问题

var maxTotalReward = function (rewardValues) {
    rewardValues = rewardValues.sort((a, b) => a - b)
    const dp = new Array(rewardValues[rewardValues.length - 1] * 2).fill(false)
    dp[0] = true
    dp[rewardValues[0]] = true
    for (let index = 1; index < rewardValues.length; index++) {
        const rewardValue = rewardValues[index]
        for (let indey = 2 * rewardValues[index] - 1; indey >= rewardValues[index]; indey--) {
            dp[indey] = dp[indey] || dp[indey - rewardValue]
        }
    }
    for (let index = dp.length - 1; index >= 0; index--) {
        if (dp[index] == true) {
            return index
        }
    }
    return 0
};

至此就实现了dp的推测和状态压缩

wuxin0011

这题周赛第四题没错出，第三题简化版倒是做出了，没想到是 bitset db ，第一次遇到，以后遇到这种题用 python 最方便

f = 1
for x in sorted(set(a)):
    m = f & ( (1 << x) - 1)
    f |= m << x
return f.bit_length() - 1