BZOJ 4976 [Lydsy1708月赛]宝石镶嵌

本文主要是介绍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\n",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\n",ans);
33     }
34     return 0;
35 }

View Code

 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\n",m,sum);
21     if(n-k>=m) printf("%d\n",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\n",ans);
32     }
33     return 0;
34 }