BZOJ4976: [Lydsy1708月赛]宝石镶嵌

BZOJ4976: [Lydsy1708月赛]宝石镶嵌

https://lydsy.com/JudgeOnline/problem.php?id=4976

分析:

• 本来是从\(k\le 100\)这里入手，想了想还是不能列出一个和\(k\)有关的式子。
• 看到\(n\)有点大了，当\(n-k>log\)的时候显然能全取到。
• 否则\(n\le k+log\)不超过\(117\)，暴力即可 。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 131080
int n,K,a[N];
int f[120][N];
int Cnt(int x) {
    return x?(Cnt(x>>1)+(x&1)):0;
}
inline void upd(int &x,int y) {x=x<y?x:y;}
int main() {
    scanf("%d%d",&n,&K);
    int i,o=0,j;
    for(i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        o|=a[i];
    }
    int k=Cnt(o);
    if(n-K>=k) return printf("%d\n",o),0;
    
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(i=0;i<n;i++) {
        for(j=0;j<=131072;j++) {
            upd(f[i+1][j|a[i+1]],f[i][j]+1);
            upd(f[i+1][j],f[i][j]);
        }   
    }
    int lim=n-K;
    for(i=131072;i>=0;i--) {
        if(f[n][i]<=lim) {
            printf("%d\n",i); return 0;
        }
    }
}

BZOJ4976: [Lydsy1708月赛]宝石镶嵌

原文：https://www.cnblogs.com/suika/p/10165844.html