P1441 砝码称重 状压+bitset的组合()-其他

P1441 砝码称重 状压+bitset的组合()

这道题最妙的是移入bitset，来统计能组成那些数

令bitset<2010> S;

一开始初始化S[0]=1

对于w[i],S<

但原本的数我们依旧是要的，所以便是S=S|(S<

S.count返回S中1的个数，但是无符号的数据类型要转int，注意要减去(S[0]=1)这种不合法情况

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
const int N=30;
//const int M=;
//const int inf=0x3f3f3f3f;     
//const ll INF=0x3ffffffffffff;
int T,n,m,w[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    n=read(),m=read();
    for(int i=0;i<=n-1;i++) w[i]=read();
    int ans=0;
    for(int i=0;i<(1<<n);i++)
    {
        if(__builtin_popcount(i)==n-m)
        {
            bitset<2010> S;
            S[0]=1;
            for(int j=0;j<=n-1;j++)
                if(i&(1<<j)) S=S|(S<<w[j]);
            ans=max(ans,(int)S.count()); 
        }
    }
    printf("%d",ans-1);
    return 0;
}

————————

这道题最妙的是移入bitset，来统计能组成那些数

令bitset<2010> S;

一开始初始化S[0]=1

对于w[i],S<

但原本的数我们依旧是要的，所以便是S=S|(S<

S.count返回S中1的个数，但是无符号的数据类型要转int，注意要减去(S[0]=1)这种不合法情况

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
const int N=30;
//const int M=;
//const int inf=0x3f3f3f3f;     
//const ll INF=0x3ffffffffffff;
int T,n,m,w[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    n=read(),m=read();
    for(int i=0;i<=n-1;i++) w[i]=read();
    int ans=0;
    for(int i=0;i<(1<<n);i++)
    {
        if(__builtin_popcount(i)==n-m)
        {
            bitset<2010> S;
            S[0]=1;
            for(int j=0;j<=n-1;j++)
                if(i&(1<<j)) S=S|(S<<w[j]);
            ans=max(ans,(int)S.count()); 
        }
    }
    printf("%d",ans-1);
    return 0;
}