洛谷 - P1441 砝码称重

#题面

#题目描述

现有 $n$ 个砝码，重量分别为 $a_i$，在去掉 $m$ 个砝码后，问最多能称量出多少不同的重量（不包括 $0$）。

请注意，砝码只能放在其中一边。

#输入格式

第 $1$ 行为有两个整数 $n$ 和 $m$，用空格分隔。

第 $2$ 行有 $n$ 个正整数 $a_1, a_2, a_3, \ldots, a_n$，表示每个砝码的重量。

#输出格式

仅包括 $1$ 个整数，为最多能称量出的重量数量。

#输入输出样例

样例输入 #1

3 1
1 2 2

样例输出 #1

3

样例解释 #1

在去掉一个重量为 $2$ 的砝码后，能称量出 $1, 2, 3$ 共 $3$ 种重量。

#数据范围与约定

• 对于 $20\%$ 的数据，$m = 0$；
• 对于 $50\%$ 的数据，$m \leq 1$；
• 对于 $50\%$ 的数据，$n \leq 10$；
• 对于 $100\%$ 的数据，$n \leq 20$，$m \leq 4$，$m < n$，$a_i \leq 100$。

#思路

观察数据范围，可以发现所有砝码组成的重量最大不超过 $2000$，考虑使用 bitset 维护。

在 $[0 \sim 2^n)$ 范围内枚举状态，第 $k$ 位表示第 $k$ 个砝码是否存在。当 $\text{popcount}(i) = n - m$ 时，状态 $i$ 可以更新答案。

显然重量 $0$ 不需要任何砝码即可称量出，因此直接设置第 $0$ 位为 $1$。然后对于所有的砝码，计算其与前面的砝码搭配能称出的重量，最后二进制下为 $1$ 的位的个数即为当前状态下的结果。据此更新答案即可。

由于最终结果不能包括 $0$，因此需要在最终答案中 $- 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <iostream>
#include <bitset>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 20;

int n, m, a[N], ans;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < 1 << n; i++) {
        if (__builtin_popcount(i) == n - m) {
            std::bitset<2005> s;
            s[0] = 1;

            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    s |= s << a[j];
                }
            }

            ans = std::max(ans, (int)s.count());
        }
    }

    cout << ans - 1 << endl;

    return 0;
}