题解 [email protected]洛谷 | [email protected] 【Maximum Subsequence Value】

思路:

考虑如何使取出的 kk 个数价值最大。

对于 k{1,2,3}k\in\left\{1,2,3\right\},根据定义,若 kk 个数中至少有一个数的二进制位 ii 上是 11,则价值增加 2i2^i,这个定义十分眼熟,发现就是按位或的结果。对于 k4k\ge 4kk 每增加 11,就会使 max(1,k2)\max\left(1,k-2\right) 增加 11,因此每个二进制位的出现次数都需要加 11 才能使答案更优,显然不如 k=3k=3 的情况。

因此对于 n{1,2}n\in\left\{1,2\right\},答案即为这些数的或;对于 n3n\ge 3,答案为数列任取三个数能得到的最大的或。可以花费 O(n3)\mathcal{O}(n^3) 枚举取的三个数得到答案。

因为懒得特判前者,我选择牺牲了一定的代码常数,将 i,j,ki,j,k 都从 11 枚举到 nn,但是对于前者也能得到正确的结果。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 ll T; for(scanf("%lld", &T);T;T--)
#define mulT1 ll T, rnds; for(scanf("%lld", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const ll N = 505;

ll n, a[N], ans;

int main() {
	scanf("%lld", &n);
	rep(i, 1, n) scanf("%lld", &a[i]);
	rep(i, 1, n) rep(j, 1, n) rep(k, 1, n) ans = max(ans, a[i]|a[j]|a[k]);
	printf("%lld\n", ans);
	return 0;
}