1.題目：

給你一個(gè)整數(shù)數(shù)組?rewardValues，長度為?n，代表獎(jiǎng)勵(lì)的值。

最初，你的總獎(jiǎng)勵(lì)?x?為 0，所有下標(biāo)都是?未標(biāo)記?的。你可以執(zhí)行以下操作?任意次?：

• 從區(qū)間?[0, n - 1]?中選擇一個(gè)?未標(biāo)記?的下標(biāo)?i。
• 如果?rewardValues[i]?大于?你當(dāng)前的總獎(jiǎng)勵(lì)?x，則將?rewardValues[i]?加到?x?上（即?x = x + rewardValues[i]），并?標(biāo)記?下標(biāo)?i。

以整數(shù)形式返回執(zhí)行最優(yōu)操作能夠獲得的?最大?總獎(jiǎng)勵(lì)。

示例 1：

輸入：rewardValues = [1,1,3,3]

輸出：4

解釋：

依次標(biāo)記下標(biāo) 0 和 2，總獎(jiǎng)勵(lì)為 4，這是可獲得的最大值。

示例 2：

輸入：rewardValues = [1,6,4,3,2]

輸出：11

解釋：

依次標(biāo)記下標(biāo) 0、2 和 1?？偑?jiǎng)勵(lì)為 11，這是可獲得的最大值。

提示：

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

該作者解決方法：

不知道C語言要怎么建構(gòu)bitset，看了其他人的解答后嘗試用位運(yùn)速加速。 假設(shè)有一個(gè) bool 數(shù)組 dp。在每一次循環(huán)中，dp[rewardValues[i] + j] 可以由 dp[j] 轉(zhuǎn)移而來，其中 j 為小于 rewardValues[i] 的非負(fù)整數(shù)。 為了加速運(yùn)算并減少空間浪費(fèi)，可以將 bool 數(shù)組改成 unsigned long long。 在C語言中，雖 bool 使用1bit，但最小尋址單位為1字節(jié)，所以占用1字節(jié)。 現(xiàn)在我們將數(shù)組聲明成 unsigned long long，此時(shí)每次操作最多可以操作64個(gè)位元，也就是64個(gè)狀態(tài)。 由于 rewardValues[i] 不一定為64的倍數(shù)，為了避免發(fā)生溢位的狀況，必須將 dp[j] 所代表的64位元拆成兩部分。 為了計(jì)算正確的下標(biāo)，我們把 rewardValues[i] 用 index 與 digit 表示，其中 rewardValues[i] = 64 * index + digit：

index = rewardValues[i] / 64

digit = rewardValues[i] % 64

因此，對于每個(gè)下標(biāo) j，dp[j] 可拆成：

(dp[j] & ((1 << (64 - digit)) - 1)) << digit

dp[j] >> (64 - digit)

假設(shè) rewardValues[i] = 65，那么：

index = 65 / 64 = 1

digit = 65 % 64 = 1

以 dp[0] 的 0 ~ 63 位為例，0 ~ 62 位可以移到 dp[index + 0] 中的 1 ~ 63 位，對應(yīng)數(shù)字 65 ~ 127。而剩下的1個(gè)位則放入 dp[index + 1] 的第 0 位，這個(gè)過程通過或運(yùn)算即可。

dp[index + j] |= (dp[j] & ((1 << (64 - digit)) - 1)) << digit;

dp[index + j + 1] |= dp[j] >> (64 - digit);

若 rewardValues[i] 為 64 的倍數(shù)可直接轉(zhuǎn)移，不需拆分

代碼：

int cmp(const void *a, const void *b)
{return *(int*)a > *(int*)b;
}int maxTotalReward(int* rewardValues, int rewardValuesSize)
{qsort(rewardValues, rewardValuesSize, sizeof(int), cmp);int size = rewardValues[rewardValuesSize - 1] / 32 + 2;unsigned long long dp[size], temp, mask;memset(dp, 0, sizeof(unsigned long long) * size);int index, digit;dp[0] = 1;for (int i = 0; i < rewardValuesSize; ++i) {index = rewardValues[i] / 64;digit = rewardValues[i] % 64;mask = digit ? (1ULL << (64 - digit)) - 1 : 0;for (int j = 0; j < index; ++j){if (digit) {dp[j + index] |= (dp[j] & mask) << digit;dp[j + index + 1] |= dp[j] >> (64 - digit);} else {dp[j + index] |= dp[j];}}if (digit) {temp = dp[index] & ((1ULL << digit) - 1);dp[2 * index] |= (temp & mask) << digit;dp[2 * index + 1] |= temp >> 64 - digit;}}for (int i = size - 1; i >= 0; --i) {if (dp[i])return 64 * i + 63 - __builtin_clzll(dp[i]);}return 0;
}

聲明：來源力扣題解

作者：borane

鏈接：https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/solutions/2805771/01bei-bao-wei-yun-suan-by-modest-nashdn2-svmq/

來源：力扣（LeetCode）