力扣10.26

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

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

• 从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
• 如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i]加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。

以整数形式返回执行最优操作能够获得的 最大 总奖励。

数据范围

• 1 <= rewardValues.length <= 5 * 104
• 1 <= rewardValues[i] <= 5 * 104

分析

参考灵神的题解
最初想法是定义$f[i][j]$能否从前i个数中获得总奖励为$j$，若能则为true状态转移如下：

• 考虑能否选第i个数，假设第$i$个数为v
  • 不选v：$dp[i][j]=dp[i-1][j]$
  • 选v：$dp[i][j]=dp[i-1][j-v]$
• 因此$dp[i][j]=dp[i-1][j]|dp[i-1][j-v]$

考虑到$dp[i][j]$都只使用前$i-1$个的状态，因此可以使用滚动数组优化掉i这一维
但这样复杂度还是$O(n^2)$，因此还得优化，考虑使用bitset
将一维数组压缩成一个二进制数f，从低到高若第i位为$f[i]=1$则表示对应的$dp[i]$为$true$
接下来考虑$dp[i][j]=dp[i-1][j]|dp[i-1][j-v]$怎么使用位运算替换
考虑特例$v=2$，在执行上面的状态转移时

• $dp[0]ORdp[2]$中
• $dp[1]ORdp[3]$中
• …

因此若转化为二进制数f，实际是将f的低$v$位先左移$v$位再$OR$到$f$中
具体来说可以这样变，下式中$maxn$为二进制数f的位数

• $f|=f<<(maxn)-v)>>(maxn-2\ast v)$
  • 刚开始左移$maxn-v$是为了将低v位左边的数全清零（将最低位的v位移到最高位）
  • 再右移回去，这样就保证了高位都为0，可以直接异或到f中
    这样就可以将复杂度再除以32（这是因为使用了bitset）

代码

class Solution {
public:
    const static int N = 1e5 + 5;
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        bitset<N> f{1};
        for(auto v : rewardValues) {
            int move = f.size() - v;
            f |= f << move >> (move - v);
        }
        for(int i = rewardValues.back() * 2 - 1; i >= 0; i -- ) {
            if(f.test(i)) {
                return i;
            }
        }
        return 0;
    }
};

bitset

• 初始化：
  • bitset<N> b1：初始化长度N位bitset
  • bitset<N> b1(k)：使用二进制整数k初始化长度N位bitset
  • bitset<N> b3(string)：使用二进制字符串string初始化长度N为bitset
• b.any()：是否存在为1的二进制位
• b.count()：值为1的二进制位个数
• b[pos]：获取pos处的值
• b,test(pos)：pos处值是否为1
• b.set(pos)：将pos处值设置为1
• b.reset()：全设置为0
• b.set()：全设置为1