D. Bank Security Unification

D. Bank Security Unification

https://codeforces.ml/group/MKpYqfAQQQ/contest/401639/problem/D

题意

给你一个数列 你可以选择一个子序列(可以不连续) 这个序列的贡献就是选出的子序列中每相邻两个数的按位与和\(/sum_i=1^k f[i]^f[i+1]\)

思路

容易想到一个\(n^2\)的dp做法 \(dp[i] = max(dp[j] + a[j]&a[i], dp[i])\) dp[i]代表前选第i个的最优解
对于i j k 相邻的三个数 如果\(f[i]&f[k]\)的最高位是p 而\(f[i]&f[j]\)和\(f[j]&f[k]\)该位上都是1 那么选择i j k比只选择i j更优
所以我们可以在dp转移时记录一下每个二进制位上离当前位置最近的1的位置序号 然后当前位置只要那几个相应二进制位为1的位置转移过来就好了
时间复杂度为 \(O(n^2)\) 到\(O(nlgn)\)

#include<bits/stdc++.h>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;

const int N = 1e6 + 5;
ll n, a[N], dp[N], g[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        //dp[i] = a[i];
        for (ll j = 40; j >= 0; j--) {
            dp[i] = max(dp[i], dp[g[j]] + (a[g[j]] & a[i]));
            if ((1ll << j) & a[i]) g[j] = i;//更新第i位为1的位置
        }
    }
    ll mx = 0;
    for (int i = 0; i <= n; i++) mx = max(dp[i], mx);
    cout << mx << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    //cin >> _t;
    while (_t--)
        solve();
    return 0;
}