题解 P1441 【砝码称重】

pantw

2018-01-27 11:49:29

Solution

bitset好题啊! 首先用一个0到$2^n-1$的循环枚举状态,然后用popcount判断是否满足条件。 因为CCF规定不能使用下划线开头的内建函数所以我们只好自己写一个QAQ 实现方法见代码。 ~~其实一般都是打65536的表只是我懒emmm~~ 对于满足限制的状态我们用bitset大法计算答案即可。 实现细节详见代码。 ```cpp #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; } ```