【bzoj 4976】宝石镶嵌(贪心、高位前缀和)
【bzoj 4976】宝石镶嵌(贪心、高位前缀和)
传送门biu~
当n-k>=16时,每一位上的1都可以出现,只需要考虑每位是否有1即可。
剩下的情况n最大只有115(数据范围瞬间变得友善了)。
令f[state]代表组合出state最少需要多少个数,跑背包即可。然后再将f[state]更新成组合出包含state这个集合的数最少需要多少个数,枚举每个状态的子集从大到小更新即可。
计算答案时,从高位到低位贪心,只要f[state]<=n-k,即说明state状态合法。
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,k,ans,a[N],f[N<<1];
int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;++i) scanf("%d",&a[i]);if(n-k>=16){for(int i=1;i<=(1<<16);i<<=1){for(int j=1;j<=n;++j){if(a[j]&i){ans|=i;break;}}}printf("%d",ans);return 0;}memset(f,0x3f,sizeof f);f[0]=0;for(int i=1;i<=n;++i){for(int j=(1<<17)-1;~j;--j){f[j|a[i]]=min(f[j|a[i]],f[j]+1);}}for(int i=(1<<17)-1;~i;--i){for(int j=1;j<=(1<<16);j<<=1){if(i&j) f[i^j]=min(f[i^j],f[i]);}}for(int i=(1<<16);i;i>>=1){if(f[ans|i]<=n-k) ans|=i;}printf("%d",ans);return 0;
}
最新文章
- springboot项目搭建0000
- 【时间复杂度】时间复杂度
- Platform 概述
- c语言中 #include < > 和include “ “的区别
- gridview的ButtonField
- LRUCache算法
- Lion蠕虫
- [转]MinGW与MSYS
- HTML超出文本显示省略号...[text
- vss使用说明!!
- Element
- 什么是Nofollow
- 【TCP专题】TCP连接断开
- Solidity介绍
- jmeter脚本录制入门详解
- jsp中文传值到java乱码
- Python try...except...时捕获异常时具体文件和行数
- (Python)异常处理try...except、raise
- python笔记—>网页爬虫
- Shiro(三) Shiro核心原理分析