3685. 含上限元素的子序列和

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

考点

  • 01背包
  • 双指针

思路

按照暴力动归的思路，设f[i][j][k]为x = i阶段下的01背包，但显然会超时

对于样例nums = [4, 3, 2, 4], k = 5，当x = 3时，要做的事就是两件：

  1. 比3小的进行01背包
  2. 求出大于等于3的个数cnt，也就是说有cnt个3
  3. 暴力枚举k - (0 ~ cnt) * 3，看看01背包里是否有这个值； 如果有，则说明小于3的序列+大于等于3序列能凑出和为k的新序列

排序后，从左到右只需要做一次01背包即可，每次只需要对nums[i] == x的数进行01背包，因为比x小的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
26
27
28
class Solution {
 public:
  static const int maxn = 4e3 + 50;
  vector<bool> subsequenceSumAfterCapping(vector<int>& nums, int K) {
    bool f[maxn];
    int n = nums.size();
    vector<bool> ans(n, 0);
    //
    sort(nums.begin(), nums.end());
    memset(f, 0, sizeof(f)), f[0] = 1;
    int idx = 0;
    for (int x = 1; x <= n; ++x) {
      while (idx < n && nums[idx] == x) {
        for (int j = K - nums[idx]; j >= 0; --j) {
          if (f[j]) f[j + nums[idx]] = 1;
        }
        ++idx;
      }
      for (int i = 0; i <= min(n - idx, K / x); ++i) {
        if (f[K - i * x]) {
          ans[x - 1] = 1;
          break;
        }
      }
    }
    return ans;
  }
};

使用位运算优化后得到的第二版：

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
class Solution {
 public:
  static const int maxn = 4e3 + 50;
  vector<bool> subsequenceSumAfterCapping(vector<int>& nums, int K) {
    bitset<maxn> f;
    int n = nums.size();
    vector<bool> ans(n, 0);
    //
    sort(nums.begin(), nums.end());
    f[0] = 1;
    int idx = 0;
    for (int x = 1; x <= n; ++x) {
      while (idx < n && nums[idx] == x) {
        f |= f << nums[idx];
        ++idx;
      }
      for (int i = 0; i <= min(n - idx, K / x); ++i) {
        if (f[K - i * x]) {
          ans[x - 1] = 1;
          break;
        }
      }
    }
    return ans;
  }
};