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

题干

给你一个整数数组 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⁴

思路

首先，题目要求选择的rewardValues[i]>x，那么先选较大的值就无法再选择较小的值，因此应该先选较小的值再选较大的值，开始前先对rewardValue进行排序。

另外，对于两个数a1 == a2，如果选择了a1，那么x+a1>a2（或者a1 == a2），a2就不可能再被选择，也即不可能选择两个值相同的数，因此可以对数组进行去重。

记max(rewardValues) = m，本题可以得到的最大总奖励最多为 2 * m-1。将问题化为子问题进行分析：考虑对于一个数y，如果要选择数y，那么一定有当前的总奖励x < y，即x最大可能为y-1，假设y的下标为i，该情况可以描述为选择前i个数的最大总奖励的最大可能值为 2 * y-1。因此，对于整个数组，可以得到的最大总奖励最多为 2 * m-1。

排序后，本题可以描述为0-1背包问题，dp[i][j]表示前i个数可以取得的最大总奖励j，对于第i个数，只有选或者不选两种情况。

• 选，需满足 j - rewardValues[i] < rewardValues[i] 和 j - rewardValues[i] >= 0，即 rewardValues[i] <= j < 2*rewardValues[i]，dp[i][j] = dp[i-1][j-rewardValues[i]]。
• 不选，dp[i][j] = dp[i-1][j]。

因此 dp[i][j] = dp[i-1][j] || dp[i-1][j-rewardValues[i]]，最终结果为dp[n][j]。

但是本题的数据量较大，需要去掉第一重维度，那么就变成dp[j] = dp[j] | dp[j-rewardValues[i]]，再使用bitset优化，将一维的数组转为二进制数，二进制位第j位 f[j] = 1表示可以取到j这个值，f[j] = 0表示无法取到j这个值，也可以用true和false来表示是否可以取到该值。考虑数组A={2,3,4}的求解过程。

用一个bitset数组f来表示是否可以得到某一个值（实际上f是一个二进制数，这里带下标只是为了解释原理），f[i]表示前i个数能得到的值，如果该最大奖励值能由不多于i个数取到，则fi为true，f的大小为 2 * m-1。以二进制的方式表示，其中选择0个数时f = 10000000，选择第一个数时f = 10100000，选择前两个数时f = 10110100，表示可以得到2、3、5，选择前三个数时f=10111111，表示可以得到2、3、4、5、6、7。

分析f3，可以看出，取rewardValues[i] = 4时，需要考虑f[0]、f[1]、f[2]和f[3]，也即，如果f[0]、f[1]、f[2]和f[3]为1，那么f[0]、f[1]、f[2]和f[3]加上4就可以得到f[4]、f[5]、f[6]和f[7]为1。记rewardValues[i]为v，相当于取f的低v位，向高位移动v位，再与高位进行or运算，得到是否能取到高位对应的v个值（上图中左侧实际上对应bitset数组的低位）。实际上遍历rewardValues进行对f的更新的过程就是考虑选择或者不选择某个值v时可以得到的最大奖励值。

eg：选择前一个数时f=00000101，选择前两个数时，可选择的数是3，将f的低三位左移len-3位，再右移len-6位，得到00101000，与f=00000101进行或运算，得到f=00101101。

代码：

int maxTotalReward(std::vector<int> &rewardValues)
{
    //该部分优化为：记一下rewardValues的最大值m，如果有一个数等于m-1或者有两个数相加等于m-1，那么结果一定为2*m-1
    int m = std::ranges::max(rewardValues);
    std::unordered_set<int> us;
    for (auto &i : rewardValues)
    {
        if (us.contains(i))
        {
            continue;
        }
        if (i == m - 1 || us.contains(m - 1 - i))
        {
            return 2 * m - 1;
        }
        us.insert(i);
    }
    //该部分对rewardValues进行排序，并去重
    std::ranges::sort(rewardValues);
    rewardValues.erase(std::unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
    std::bitset<100000> f{1};
    //记f.size()=len，f先左移f-i位，把低i位全部移到最高位，其余低位为0
    //然后右移len-i-i位，相当于把原来的低i位，向左移动了i位，其余位全部置0，即得到一个类似00000xxxx0000的二进制数
    for (auto &i : rewardValues)
    {
        f |= f << (f.size() - i) >> (f.size() - i * 2);
    }
    //从最大的可能值开始向前查询是否存在结果
    for (int i = rewardValues.back() * 2 - 1; ; --i)
    {
        if (f.test(i))
        {
            return i;
        }
    }
}

优化前复杂度为 5 * 10⁴ * 2 * 5 * 10⁴ = 5 * 10⁹，优化后复杂度为 5 * 10⁹/ w，w为表示数组bitset需要的二进制位数，一般为64或32。