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

发表于 分类于 阅读次数： Waline： 本文字数： 122 阅读时长 ≈ 1 分钟

考点

  • 01背包
  • 贪心
  • 位运算

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        int n = unique(rewardValues.begin(), rewardValues.end()) -
                rewardValues.begin();
        bitset<4001> f;
        f[0] = 1;
        int m = 0;
        for (int i = 0; i < n; ++i)
            m = max(m, rewardValues[i]);
        m = m * 2 - 1;
        for (int i = 0; i < n; ++i) {
            int x = rewardValues[i];
            bitset<4001> t;
            t.flip();
            f |= ((t >> (4001 - x)) & f) << x;
        }
        for (int j = m; j >= 0; --j) {
            if (f[j])
                return j;
        }
        return 0;
    }
};

思路

3181. 执行操作可获得的最大总奖励 II的简化版，直接参考它的题解即可