(状压dp)1655. 分配重复整数

1655. 分配重复整数

class Solution {
 public:
  bool canDistribute(vector<int>& nums, vector<int>& qs) {
    map<int, int> mp;
    for (auto i : nums) mp[i]++;
    vector<int> cnt;
    for (auto p : mp) cnt.push_back(p.second);
    int n = cnt.size(), m = qs.size();
    bool f[n + 1][1 << m];
    int sum[1 << m];
    memset(sum, 0, sizeof sum);
    memset(f, 0, sizeof f);

    for (int mask = 0; mask < 1 << m; mask++)
      for (int j = 0; j < m; j++) {
        if (mask & (1 << j)) {
          sum[mask] = sum[mask ^ (1 << j)] + qs[j];
        }
      }
    for (int i = 0; i <= n; i++) f[i][0] = true;
    for (int i = 1; i <= n; i++) {
      for (int mask = 0; mask < 1 << m; mask++) {
        f[i][mask] = f[i - 1][mask];
        for (int sub = mask; sub; sub = (sub - 1) & mask) {
          if (sum[sub] <= cnt[i - 1]) {
            f[i][mask] |= f[i - 1][mask ^ sub];
          }
        }
      }
    }

    return f[n][(1 << m) - 1];
  }
};