【bzoj4976】宝石镶嵌乱搞+dp

题目描述

从$n$个数中选出$n-k$个，使得它们的二进制或（or）最大。输出这个值。

输入

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

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

输出

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

样例输入

4 1
32 16 8 7

样例输出

题解

乱搞+dp

由于上限为$100000$，因此最多只有$17$个二进制位。

考虑当可以保留的数的个数$n-k\ge 17$时，显然对于每一位选出一个该位为$1$的数，选出来的数一定不超过$17$个。因此一定能够占满所有的二进制位。所以所有的数的二进制或即为答案。

当$n-k<17$时，由于$k$只有$100$，所以$n$只有$117$，因此可以暴力dp。设$f[i][j]$表示能否选出$i$个数使得它们的二进制或为$j$。然后随便转移即可。

时间复杂度$O(117*17*2^{17})$。

#include <cstdio>

bool f[17][131080];

int main()

{

	int n , m , i , x , ans;

	scanf("%d%d" , &n , &m);

	if(n - m >= 17)

	{

		ans = 0;

		for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , ans |= x;

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

	}

	else

	{

		f[0][0] = 1;

		int j , k;

		for(i = 1 ; i <= n ; i ++ )

		{

			scanf("%d" , &x);

			for(j = 0 ; j < n - m ; j ++ )

				for(k = 0 ; k < 131072 ; k ++ )

					f[j + 1][k | x] |= f[j][k];

		}

		for(i = 131071 ; ~i ; i -- )

			if(f[n - m][i])

				return printf("%d\n" , i) , 0;

	}

	return 0;

}

巴特西

【bzoj4976】宝石镶嵌乱搞+dp

最新文章

热门文章

巴特西

【bzoj4976】宝石镶嵌 乱搞+dp

最新文章

热门文章

【bzoj4976】宝石镶嵌乱搞+dp