题意

要求分成恰好 组,每组的权值为 。要求最大化

分析

和位运算有关系,我们就要想到拆位。由于是要最大化权值,所以我们肯定是要优先满足高位。而每一位独立,所以我们可以直接枚举位数。定义 表示前 个已经分成了 组,是否可以组成当前答案, 表示现在枚举的答案。那么转移为 。那么最后是否成立就看 是否成立了。总复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 110;
bool f[N][N];
ll s[N],n,k,ans = 0;
bool check(ll x) {
    memset(f,0,sizeof(f));f[0][0] = 1;
    for(ll i = 1;i <= n;i++) {
        for(ll j = 0;j < i;j++) {
            for(ll K = 1;K <= k;K++) {
                f[i][K] |= (f[j][K - 1] & (((s[i] - s[j]) & x) == x));
            } 
        }
    }
    return f[n][k];
}
int main() {
    cin >> n >> k;
    for(ll i = 1;i <= n;i++) {
        ll x;cin >> x;s[i] = s[i - 1] + x;
    }for(ll i = 60;~i;i--) {
        ll res = (ans | (1ll << i));
        if(check(res)) ans = res;
    }cout << ans << endl;
}