P1441 砝码称重 + 状压dp思路

题意

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

对于 $100\%$ 的数据，$n\leq 20$， $m\leq 4$，$m < n$，$a_i\leq 100$。

思路

什么是状态压缩

二进制，只有 $0$ 与 $1$，但是不光可以从数字上看，它也可以表示“有”与“没有”。

比如本题，一个长度为 $4$ 的序列，我们可以用 $1001$ 来表示第一个没有了，第二，三个还留着，第四个也没有了。那么，本来一个很长的序列就可以转换成一个数字了——$1001=9$。状压dp通常适合长度较小，但是需要枚举所有状态的问题。

如何设计状压dp

不要本能地把所有的状态看成一个个数字，而就是一个个“有无无有”的状态。也不要从数字上考虑位运算符，而就是比较两个状态的工具，比如 $\&$ 是比较两个之间是否相同，得到的新状态。

本题思路

我们将 $1$ 设为拿走了，$0$ 设为没拿走。之后枚举所有的状态，如果正好拿走的个数为 $n-m$, 我们再去判断答案，也就是把没拿走的去枚举状态。之后判断每一个是否为 $1$。

tips

可以使用 $bitset$ 进行二进制计算。$bitset$ 的速度比正常数组快 $64$ 倍。但是不要尝试手写，$bitset$ 比一般的手写要快。

代码

#include <iostream>
#include <bitset>
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
ll num_one(ll x){
    ll num=0;
    while (x){
        num+=(x&1);
        x>>=1;
    }
    return num;
}
ll w[MAXN];
int main() {
    ll n,m;
    cin>>n>>m;
    for (int i = 1; i <=n ; ++i) {
        cin>>w[i];
    }
    ll sz=(1<<n),ans=0;
    for (int i = 1; i <=sz-1 ; ++i) {
        if(num_one(i)==n-m){
            bitset<10000>s;
            s[0]=true;
            for (int j = 1; j <=n ; ++j) {
                if(i&(1<<(j-1))){
                    s=s|(s<<w[j]);
                }
            }
            ans= max(ans,ll(s.count())-1);
        }
    }
    cout<<ans<<endl;
    return 0;
}
复制代码