题解 P1441 【砝码称重】

思路：$01$ 背包方案数 + bitset + 子集枚举。 首先我的 dfs 菜的一匹，所以说一看这道题我就放弃了 dfs。 我们考虑子集枚举选取 $n-m$ 个物品时的状态，然后对于每一个状态进行一次 $bool$ 类型的 $01$ 背包，最后统计 $\max$ 即可。 但是显然我们的复杂度会达到 $$ T(n) = 2^n \times (n \sum a_i + 3n) -> \Theta(2^nn\sum a_i) $$ 其中第一项是枚举子集的复杂度，之后是 $01$ 背包方案数 + 扫一遍 + 清零+求出背包容量 $t$ 的复杂度。 显然不足以 $1s$ 过。那么我们不妨思考一个简单的优化，我们枚举状态从 `1 <<(n - m - 1)` 开始，因为当位数小于 $n - m$ 时，永远选不够 $n-m$ 个。并且我们可以预处理出每个状态的 $1$ 的个数，那么我们就会有 $$ \begin{aligned} T(n) &= 2^n-2^{n-m} +C_{n}^{m}\cdot (n \sum a_i + 3n) \\ &=\Theta(\max(2^n - 2^{n-m}, C_{n}^{m} \cdot n\sum a_i)) \end{aligned} $$ 好像还可以的吧，但事实上我们还可以更优，我们直接考虑用$bitset$作为$dp$数组，然后就会有 $3 \cdot\frac{n}{32}$ 的检测代价，好像可以优化些常数。 最后我还用了 ```cpp inline int max(int a, int b) {return b - (b - a & (b - a >> 31));} ``` 的毒瘤优化，但是依旧很慢——不过这不能阻止人类否定$dfs$的一家独大。 $qwq$ ```cpp #include <bitset> #include <cstdio> #include <iostream> #define MAX 5000 using namespace std ; int i, j, k, d, t ; bitset <MAX> dp ; int N, M, base[MAX], Len[MAX << 8], Max, Ans ; inline int max(int a, int b) {return b - (b - a & (b - a >> 31));} int main(){ cin >> N >> M ; d = N - M, Max = (1 << N) - 1 ; for (i = 1 ; i <= N ; ++ i) cin >> base[i] ; for (i = 1 ; i <= Max ; ++ i) Len[i] = Len[i - (i & -i)] + 1 ; for (i = 1 << d - 1; i <= Max ; ++ i){ if(Len[i] == d){ dp.reset(), dp[0] = 1, t = 0 ; for (j = 0 ; j < N ; ++ j) t += (1 << j & i) ? base[j + 1] : 0 ; for (k = 0 ; k < N ; ++ k) for (j = t ; j >= base[k + 1] ; -- j) dp[j] = (1 << k & i) ? dp[j] : (dp[j] | dp[j - base[k + 1]]) ; Ans = max(Ans, (int)dp.count() - 1) ; } } cout << Ans << endl ; return 0 ; } ``` # $by \ \ Flower\_ pks$ 作者正在奋力卡常中。。。