template <int siz> int solve(int m, const vector<int>& vec) {if (siz <= m) return solve<min(siz * 2, 1000000)>(m, vec);bitset<siz> f;f[0] = 1;for (size_t i = 0, r = 0; i < vec.size(); i = r) {++r;while (r < vec.size() && vec[r] == vec[r - 1]) ++r;for (size_t c = 1; i < r; i += c, c = min(c << 1, r - i)) {f |= f << (c * vec[i]);}}while (m && !f[m]) --m;return m;
}
solve<1>(m, vec)
返回 vec
的一个最大的“和不超过 \(m\)”的子集的和。使用倍增确定 bitset 大小,多重背包二进制拆分优化,复杂度据说是 \(O(n\sqrt n/w)\)(\(n=\sum a_i\))