题意
要求分成恰好 组,每组的权值为 。要求最大化 。
分析
和位运算有关系,我们就要想到拆位。由于是要最大化权值,所以我们肯定是要优先满足高位。而每一位独立,所以我们可以直接枚举位数。定义 表示前 个已经分成了 组,是否可以组成当前答案, 表示现在枚举的答案。那么转移为 。那么最后是否成立就看 是否成立了。总复杂度为 。
代码
#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; }