codeforces#P1365E. Maximum Subsequence Value
Maximum Subsequence Value
以下题面由 AI 翻译。
题目描述
Ridhiman 向 Ashish 发起挑战，要求他找出一个由正整数组成的数组 $a$（大小为 $n$）的最大价值子序列。
非空子序列的价值定义为：对于所有满足至少 $\max(1, k - 2)$ 个子序列元素的第 $i$ 位二进制位为 1 的 $i \ge 0$，累加 $2^i$。其中 $k$ 是子序列的元素个数。
回忆一下，$b$ 是 $a$ 的子序列，当且仅当 $b$ 可以通过删除 $a$ 中一些（可能为零）元素得到。
帮助 Ashish 找出他能通过选择 $a$ 的某个子序列获得的最大价值。
输入格式
第一行输入包含一个整数 $n$ $(1 \le n \le 500)$ ——数组 $a$ 的大小。
第二行包含 $n$ 个空格分隔的整数 ——数组的元素 $(1 \le a_i \le 10^{18})$。
输出格式
输出一个整数 ——Ashish 通过选择 $a$ 的某个子序列能获得的最大价值。
样例数据
3
2 1 3
3
3
3 1 4
7
1
1
1
4
7 7 1 1
7
样例解释
对于第一个测试用例，Ashish 可以选择大小为 2 的子序列 $\{{2, 3}\}$。2 的二进制表示为 10，3 的二进制表示为 11。由于 $\max(k - 2, 1) = 1$，子序列的价值为 $2^0 + 2^1$（两个数在第一位都为 1，且 3 在第二位为 1）。注意他也可以选择子序列 $\{{3\}$ 或 $\{{2, 1, 3\}}$。
第二个测试用例中，Ashish 选择子序列 $\{{3, 4\}$，价值为 7。
第三个测试用例选择子序列 $\{{1\}$，价值为 1。
第四个测试用例选择子序列 $\{{7, 7\}$，价值为 7。
数据范围与提示
-
数据范围：
-
提示：
- 当子序列长度为 1 或 2 时，每个位的贡献条件为至少一个元素在该位为 1。
- 当子序列长度大于等于 3 时，每个位的贡献条件为至少 个元素在该位为 1。
- 最优解可能出现在长度为 1、2 或 3 的子序列中，因为较长的子序列可能导致更严格的贡献条件。