BZOJ4976：宝石镶嵌（DP&思维）

Description

魔法师小Q拥有n个宝石，每个宝石的魔力依次为w_1,w_2,...,w_n。他想把这些宝石镶嵌到自己的法杖上，来提升

法杖的威力。不幸的是，小Q的法杖上宝石镶嵌栏太少了，他必须扔掉k个宝石才能将剩下的宝石镶嵌上去。法杖的

威力等于镶嵌在上面的所有宝石的魔力按位做或(OR)运算的结果，请写一个程序帮助小Q做出最佳的选择，使得法

杖的威力最大。

Input

第一行包含两个正整数n,k(2<=n<=100000,1<=k<=100,k<n)，分别表示宝石的个数以及要扔掉的宝石个数。

第二行包含n个整数w_1,w_2,...,w_n(0<=w_i<=100000)，分别表示每个宝石的魔力。

Output

输出一行一个整数，即最大的威力。

Sample Input

4 1
32 16 8 7

Sample Output

思路：之前遇到一个类似的题，不过是XOR不是OR，此题由于是OR，当要留的数比较多的时候一定能取到最大值，即a1|a2|...|an。

否则，我们可以dp，用dp[i][j]表示删去i个能否OR得到j。不难得到下面代码，复杂度O(17*N*1<<17)，T了。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int dp[][maxn],a[maxn],ans,Mx;

int main()

{

    int N,K; scanf("%d%d",&N,&K); K=N-K;

    for(int i=;i<=N;i++){

        scanf("%d",&a[i]);

        Mx|=a[i];

    }

    if(K>=) printf("%d\n",Mx);

    else {

        dp[][]=;

        for(int i=;i<=N;i++){

          for(int k=;k<=K;k++)

             for(int j=;j<=Mx;j++){

                dp[k][j|a[i]]|=dp[k-][j];

            }

        }

        for(int i=;i<=Mx;i++) if(dp[K][i]) ans=i;

        printf("%d\n",ans);

    }

    return ;

}

换个DP，我们用dp[i][j]表示前面i个得到j最多删去多少个，最后dp[N][i]>=K的最大i即是答案。

#include<bits/stdc++.h>

using namespace std;

const int maxn=<<;

int dp[][maxn],a[maxn],ans,Mx; //dp：最多可以删去

int main()

{

    int N,K; scanf("%d%d",&N,&K);

    for(int i=;i<=N;i++){

        scanf("%d",&a[i]);

        Mx|=a[i];

    }

    if(N-K>=) printf("%d\n",Mx);

    else {

        for(int i=;i<=N;i++) for(int j=;j<=Mx;j++) dp[i][j]=-;

        dp[][]=;

        for(int i=;i<=N;i++){

            for(int j=;j<=Mx;j++){

                dp[i][j]=max(dp[i][j],dp[i-][j]+);

                dp[i][j|a[i]]=max(dp[i][j|a[i]],dp[i-][j]);

            }

        }

        for(int i=Mx;i>=;i--) if(dp[N][i]>=K){

            ans=i; break;

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西