题解 P1441 【砝码称重】

bitset好题啊！

首先用一个0到2^n-1的循环枚举状态，然后用popcount判断是否满足条件。

因为CCF规定不能使用下划线开头的内建函数所以我们只好自己写一个QAQ 实现方法见代码。 其实一般都是打65536的表只是我懒emmm

对于满足限制的状态我们用bitset大法计算答案即可。

实现细节详见代码。

#include <bitset>
#include <cstdio>
int w[25];
int table[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
int popcount(unsigned int x) { // 返回x的二进制中1的个数
    int ret = 0;
    for(int i = 0; i < 8; i++) ret += table[x & 15], x >>= 4;
    return ret;
}
int main() {
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", w + i);
    for(int i = 0, li = 1 << n; i < li; i++) {
        if(popcount(i) == n - m) {
            std::bitset<2010> S;
            S[0] = 1;
            for(int j = 0; j < n; j++) if(i & (1 << j)) S |= S << w[j];
            int siz = S.count();
            ans = ans > siz ? ans : siz;
        }
    }
    printf("%d\n", ans - 1);
    return 0;
}