考点
思路
根据题意，规定每个数字只能接在序列和小于它的子序列尾部，求最大序列和
那么就有两条贪心策略：
- 将输入序列进行排序，从左到右依次处理，因为有效序列只能出现
1 2 5，而不可能出现5 2 1或者2 5 1
- 排序后去重，因为
1 1 2这种序列也不可能出现
- 同2，在做DP时，背包容量不会超过
最大元素 * 2 - 1，比如1 2 3 3的上限不可能是6
接下来考虑01背包的转移方程：
f[i][j]，从1 ~ i中选出容量等于j的最大价值，初值为f[0][0] = 0，f[0][1 ~ 最大元素 * 2 - 1] = 负无穷，表示不可达
考虑第i个物品：
要么不对f[i][j]有贡献，f[i][j] = f[i - 1][j]；
要么对f[i][j]有贡献，注意，由于本题限制选第i个数时，从前i - 1个数中选的序列和不能超过第i个数，所以当且仅当j - a[i] < a[i]，即j < 2 * a[i]时，才可以转移f[i][j] = f[i][j - a[i]] + a[i]；
最后结果在f[n][0 ~ 最大元素 * 2 - 1]取极值即可
至此，可以得到如下复杂度的代码（使用滚动数组去掉第一维），但仍会超时
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
26
| const int maxn = 5e4 + 50, maxm = 5e5 + 50;
class Solution {
public:
int n, W, a[maxn], f[maxm];
Solution() { n = W = 0, memset(a, 0, sizeof(a)), memset(f, 0xcf, sizeof(f)); }
int maxTotalReward(vector<int>& rewardValues) {
n = rewardValues.size();
for (int i = 1; i <= n; ++i) {
a[i] = rewardValues[i - 1];
W = max(W, a[i]);
}
W = 2 * W - 1;
sort(a + 1, a + 1 + n);
n = unique(a + 1, a + 1 + n) - (a + 1);
int res = a[1];
f[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = W; j >= a[i]; --j) {
if (j - a[i] < a[i]) f[j] = max(f[j], f[j - a[i]] + a[i]);
res = max(res, f[j]);
}
}
return res;
}
};
|
考虑优化，由于题目问的仅仅是可行性，所以没必要做计算，将转移方程修改为：
1
2
3
4
5
6
7
| f[j] = f[j]，j - a[i] >= a[i]时；
f[j] = f[j] | f[j - a[i]]，j - a[i] < a[i]时。
那么可以总结一句话，f[j] |= f[j - a[i]]， a[i] <= j < 2 * a[i]时。
初始时除f[0] = 1外其余均为0表示不可达状态，结果在f[0 ~ 最大元素 * 2 - 1] 取极值。
|
再次观察上次转移方程，发现可以使用一句位运算来替代：f |= (f & ((1 << a[i]) - 1)) << a[i];
即先取出f的低a[i]位，再左移a[i]位进行与运算，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| const int maxn = 5e4 + 50, maxm = 1e5 + 50;
class Solution {
public:
int n = 0;
bitset<maxm> f;
int maxTotalReward(vector<int>& a) {
sort(a.begin(), a.end());
n = unique(a.begin(), a.end()) - (a.begin());
f[0] = 1;
for (int i = 0; i < n; ++i)
f |= (f & bitset<maxm>((1 << a[i]) - 1)) << a[i];
for (int j = a[n - 1] * 2 - 1; j >= 0; --j)
if (f[j]) return j;
return 0;
}
};
|
但由于bitset并不支持减法，只能采用最笨的办法，先把除低a[i]位之外的位清零，即低a[i]位左移maxm - a[i]位，然后再右移maxm - 2 * a[i]后进行与运算，得到最终解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| const int maxn = 5e4 + 50, maxm = 1e5 + 50;
class Solution {
public:
int n = 0;
bitset<maxm> f;
int maxTotalReward(vector<int>& a) {
sort(a.begin(), a.end());
n = unique(a.begin(), a.end()) - (a.begin());
f[0] = 1;
for (int i = 0; i < n; ++i) {
int shift = maxm - a[i];
f |= (f << shift) >> (shift - a[i]);
}
for (int j = a[n - 1] * 2 - 1; j >= 0; --j)
if (f[j]) return j;
return 0;
}
};
|