[bzoj 4976]宝石镶嵌

[bzoj 4976]宝石镶嵌

魔法师小Q拥有n个宝石，每个宝石的魔力依次为w_1,w_2,…,w_n。他想把这些宝石镶嵌到自己的法杖上，来提升法杖的威力。不幸的是，小Q的法杖上宝石镶嵌栏太少了，他必须扔掉k个宝石才能将剩下的宝石镶嵌上去。法杖的威力等于镶嵌在上面的所有宝石的魔力按位做或(OR)运算的结果，请写一个程序帮助小Q做出最佳的选择，使得法杖的威力最大。

好吧，这道题看到或运算，就应该想到跟二进制有关。我们发现，由于或运算的特殊性，只用有一位有1就可以了。那我们只要判断一下，如果总的数的个数-k大于有1的位数的个数，那就说明扔掉k个宝石后对总的或和无影响，所以就只要输出总的或和就行了。
但如果不满足条件呢？，就dp，因为如果不满足条件，那么n小于k+有1的位数的个数，也就是说n<117，因为一个数只能有17位二进制数。f[i][j],i表示前i个数，j表示它的或和，f[i][j]就表示前i个数用了多少个数。那我们就知道如果它们的或和相等，那用的数越少越好，为什么，因为更能满足题目的条件啊。那这道题就解决了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define inf 0x3f3f3f3f
using namespace std;
int a[110000];
int f[120][(1<<17)];
bool v[20];
int main()
{int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);int ss=0;for(int j=0;j<17;j++){if((a[i]&(1<<j))>0)v[j]=true;}}int ans=0,s2=0;for(int i=0;i<17;i++){if(v[i]==true)s2++,ans|=(1<<(i));}if(n-s2>=k){printf("%d\n",ans);return 0;}memset(f,inf,sizeof(f));f[0][0]=0;for(int i=0;i<n;i++){for(int j=0;j<(1<<17);j++){if(f[i][j]!=inf){f[i+1][j]=min(f[i+1][j],f[i][j]);f[i+1][j|a[i+1]]=min(f[i+1][j|a[i+1]],f[i][j]+1);}}}for(int i=(1<<17)-1;i>=0;i--){if(f[n][i]<=n-k){printf("%d\n",i);return 0;}}
}