QOJ 1086 Bank Security Unification

令题目给定的序列为 \(a_{1\sim n}\)。

考虑到一个比较基础的 DP 是设 \(f_i\) 为以 \(a_i\) 结尾的序列的最大值。
然后转移就是 \(f_i = \max\{f_j + (a_i \& a_j)\}\)。

考虑排除掉一些不优的状态。
令 \(a_j\) 的最高位为 \(x\)，且 \(k\) 满足 \(a_k\) 最高位也为 \(x\) 且 \(k < j\)。

• 若 \(a_i\) 第 \(x\) 位为 \(1\)，那么 \(a_i\& a_j\le 2^{x + 1} - 1 < 2\times 2^x\)，于是可以知道 \(f_k\to f_i\) 肯定不如 \(f_k\to f_j\to f_i\)。
• 若 \(a_i\) 第 \(x\) 位为 \(0\)，那么若是 \(f_k\to f_i\)，贡献肯定 \(< 2^x\)，而若 \(f_k\to f_j\to f_i\)，贡献肯定 \(\ge 2^x\)。

综上，能够知道转移时只选关于每个最高位最考后的位置转移即可。

时间复杂度 \(\mathcal{O}(n\log V)\)。

#include<bits/stdc++.h>
using ll = long long;
const int maxw = 40;
ll f[maxw], s[maxw];
int main() {
   int n; scanf("%d", &n);
   for (ll x; n--; ) {
      scanf("%lld", &x);
      ll mx = 0;
      for (int i = 0; i < maxw; i++)
         mx = std::max(mx, f[i] + (s[i] & x));
      for (int i = maxw - 1; ~ i; i--) 
         if (x >> i & 1ll) {f[i] = mx, s[i] = x;} 
   }
   ll ans = 0;
   for (int i = 0; i < maxw; i++)
      ans = std::max(ans, f[i]);
   printf("%lld\n", ans);
   return 0;
}