给你
n
个整数,将其划分为恰好k
个子数组,求对每个子数组求和后按与运算的最大值
这个题和之前写过的一个最小或运算生成树类似,那个题的思路是从高位开始枚举二进制的每一位
i
,看在上一次能选的边的情况下,不选第i
位为1的边后,看能不能构成一颗生成树,如果可以构成,则最小生成树的值的第i
位是0,然后把所有边权在第i
位是1的边给删掉这个题也类似,根据贪心的思路,显然二进制高位的优先选
但是这个题的处理方式和那个不太一样,那个题可以通过删边来解除不需要选的高位产生的影响,而我们这个题不能删边,所以可以换一种方法:
首先我们写一个函数叫
check(x)
,来判断n
个数字能否分出k
个子数组,使得每个子数组求和以后进行与运算的值是x
假设在此之前已经得到的答案为
x
,则我们只需要去check
一下 x + 2 i x+2^i x+2i即可判断第i
位是否可取所以我们现在需要做的是写一个
check
函数
check
的方法是dp
,开一个
bool
类型的dp
数组,dp[i][len]
表示前i
个数字,是否存在len
个子数组的和进行与运算后得到x
显然
i
是第len
个子数组的最后一个元素,我们可以枚举一下这个子数组的左边界j
,如果 ( ( ∑ p = j i a r [ p ] ) ((\sum_{p=j}^{i}ar[p]) ((∑p=jiar[p])& x ) = = x x) == x x)==x则是说明可以进行转移,我们就让dp[i][len] |= dp[j][len-1]
判断一下
dp[n][k]
即可
#include
using namespace std;
#define int long long
#define endl '\n'
#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define m_p(a,b) make_pair(a, b)
typedef long long ll;
typedef pair<int,int> pii;
#define MAX 300050
int n, m, k, x;
ll tr[MAX];
ll sum[MAX];
ll cal(int l, int r){
return sum[r] - sum[l - 1];
}
bool dp[105][105];
bool check(ll x){
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
if((cal(j, i)&x) == x){
for(int len = 1; len <= k; ++len){
dp[i][len] |= dp[j-1][len-1];
}
}
}
}
return dp[n][k];
}
void work(){
cin >> n >> k;
for(int i = 1; i <= n; ++i)cin>>tr[i];
for(int i = 1; i <= n; ++i)sum[i] = sum[i-1]+tr[i];
ll ans = 0;
for(int i = 60; i >= 0; --i){
ans |= (1ll<<i);
if(!check(ans))ans -= (1ll<<i);
}
cout << ans << endl;
}
signed main(){
work();
return 0;
}