QOJ 1086 Bank Security Unification 题解

Link

简单题吗？考虑 DP，记 \(dp(i)\) 表示前 \(i\) 个数所能选出的最大权值，强制钦定必选 \(a_i\)。暴力枚举转移复杂度是 \(O(n^2)\)。

优化？如果 \(i, j\) 中存在一个 \(i \lt k \lt j\) 使得 \(a_i \And a_k\) 的最高位和 \(a_i \And a_j\) 的相同，因为 \(a_k\) 会多产生一次贡献，同时由于二进制高位贡献必定大于低位贡献之和，所以选 \(a_k\) 绝对是更优的。枚举 \(a_i \And a_j\) 的最高位，找到前面第一个该位为 \(1\) 的数进行转移同时记录。

复杂度是 \(O(n \log A)\)。

#include <bits/stdc++.h>using i64 = long long;constexpr int N = 1e6 + 7;
constexpr int B = 60;int n;
i64 ans;
int lst[B];
i64 a[N], dp[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cin >> n;for (int i = 1; i <= n; i++) {std::cin >> a[i];}memset(lst, -1, sizeof(lst));for (int i = 1; i <= n; i++) {for (int b = 0; b < B; b++) {if (lst[b] != -1) {int j = lst[b];dp[i] = std::max(dp[i], dp[j] + (a[i] & a[j]));}}for (int b = 0; b < B; b++) {if (a[i] & (1ll << b))lst[b] = i;}}for (int i = 1; i <= n; i++) {ans = std::max(ans, dp[i]);}std::cout << ans << "\n";return 0;
}