BZOJ 4976 [Lydsy1708月赛]宝石镶嵌
【题解】
我们设总共有m个二进制位出现过1，那么如果n-k≥m，显然所有的1都可以出现，那么答案就是把所有的数或起来。
如果n-k＜m，那么因为k不超过100，ai不超过1e5，所以n不超过117，直接n*1e5的Dp即可。
Dp的方式也是多种多样，如果设f[i][j]表示前i个数字或出j最少需要几个数字，那么转移方程为f[i][j|a[i]]=min(f[i-1][j|a[i]],f[i-1][j]+1]).
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N 131072 7 using namespace std; 8 int n,m,k,sum,ans,a[N],f[120][N]; 9 inline int read(){ 10 int k=0,f=1; char c=getchar(); 11 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 12 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 13 return k*f; 14 } 15 int main(){ 16 n=read(); k=read(); 17 for(rg int i=1;i<=n;i++) a[i]=read(),sum|=a[i]; 18 int x=sum; 19 for(rg int i=16;i;i--)if(x>=(1<<i)) m++,x-=(1<<i); 20 if(n-k>=m) printf("%d ",sum); 21 else{ 22 for(rg int i=0;i<=n;i++) 23 for(rg int j=0;j<N;j++) f[i][j]=n; 24 f[0][0]=0; 25 for(rg int i=1;i<=n;i++) { 26 for(rg int j=0;j<N;j++) 27 f[i][j|a[i]]=min(f[i][j|a[i]],f[i-1][j]+1); 28 for (rg int j=0;j<N;j++) 29 f[i][j]=min(f[i][j],f[i-1][j]); 30 } 31 for(rg int i=0;i<N;i++) if(f[n][i]<=n-k) ans=i; 32 printf("%d ",ans); 33 } 34 return 0; 35 }
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N 131072 7 using namespace std; 8 int n,m,k,sum,ans,a[N],f[120][N]; 9 inline int read(){ 10 int k=0,f=1; char c=getchar(); 11 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 12 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 13 return k*f; 14 } 15 int main(){ 16 n=read(); k=read(); 17 for(rg int i=1;i<=n;i++) a[i]=read(),sum|=a[i]; 18 int x=sum; 19 for(rg int i=16;i;i--)if(x>=(1<<i)) m++,x-=(1<<i); 20 // printf("%d %d ",m,sum); 21 if(n-k>=m) printf("%d ",sum); 22 else{ 23 for(rg int i=0;i<=n;i++) 24 for(rg int j=0;j<N;j++) f[i][j]=-n; 25 f[0][0]=0; 26 for(rg int i=1;i<=n;i++) 27 for(rg int j=0;j<N;j++) 28 f[i][j]=max(f[i][j],f[i-1][j]+1), 29 f[i][j|a[i]]=max(f[i][j|a[i]],f[i-1][j]); 30 for(rg int i=1;i<N;i++) if(f[n][i]>=k) ans=i; 31 printf("%d ",ans); 32 } 33 return 0; 34 }