首页 > 代码库 > Ural2110 : Remove or Maximize

Ural2110 : Remove or Maximize

2024-09-05 05:02:11   220人阅读

设最大的数为$w$，若$n>k+\log w$，那么显然所有$1$都可以保留，否则现在$n\leq k+\log w$。

如果$w\leq 100000$，那么可以DP，设$f[i][j]$表示考虑前$i$个数，保留的数的$or$是$j$时，最多能删除多少个数，时间复杂度$O(nw)$。

如果$w>100000$，那么$k\leq 7$，爆搜即可，时间复杂度$O(C(n,k))$。

 

#include<cstdio>#include<algorithm>using namespace std;const int N=100010;int n,m,i,j,o,ans,mx,f[2][131100],a[N];void dfs(int x,int y,int z){  if(y+n-x+1<m)return;  if(x>n){    ans=max(ans,z);    return;  }  dfs(x+1,y,z|a[x]);  if(y<m)dfs(x+1,y+1,z);}int main(){  scanf("%d%d",&n,&m);  for(i=1;i<=n;i++)scanf("%d",&a[i]),mx=max(mx,a[i]);  if(n>m+31){    for(i=1;i<=n;i++)ans|=a[i];    return printf("%d",ans),0;  }  if(mx<=100000){    for(i=0;i<131072;i++)f[0][i]=-N;    f[0][0]=0;    for(i=o=1;i<=n;i++,o^=1){      for(j=0;j<131072;j++)f[o][j]=f[o^1][j]+1;      for(j=0;j<131072;j++)if(f[o^1][j]>=0)f[o][j|a[i]]=max(f[o][j|a[i]],f[o^1][j]);    }    for(i=131071;~i;i--)if(f[o^1][i]>=m)break;    return printf("%d",i),0;  }  dfs(1,0,0);  return printf("%d",ans),0;}

　　

Ural2110 : Remove or Maximize


联系
我们