#665. 数组划分

题目描述：

给你n个整数，将其划分为恰好k个子数组，求对每个子数组求和后按与运算的最大值

思路：

这个题和之前写过的一个最小或运算生成树类似，那个题的思路是从高位开始枚举二进制的每一位i，看在上一次能选的边的情况下，不选第i位为1的边后，看能不能构成一颗生成树，如果可以构成，则最小生成树的值的第i位是0，然后把所有边权在第i位是1的边给删掉

这个题也类似，根据贪心的思路，显然二进制高位的优先选

但是这个题的处理方式和那个不太一样，那个题可以通过删边来解除不需要选的高位产生的影响，而我们这个题不能删边，所以可以换一种方法：

首先我们写一个函数叫check(x)，来判断n个数字能否分出k个子数组，使得每个子数组求和以后进行与运算的值是x

假设在此之前已经得到的答案为x，则我们只需要去check一下 x+2ix+2^ix+2i即可判断第i位是否可取

所以我们现在需要做的是写一个check函数

check的方法是dp，

开一个bool类型的dp数组，dp[i][len]表示前i个数字，是否存在len个子数组的和进行与运算后得到x

显然i是第len个子数组的最后一个元素，我们可以枚举一下这个子数组的左边界j，如果 ((∑p=jiar[p])((\sum_{p=j}^{i}ar[p])((∑p=ji​ar[p])&x)==xx) == xx)==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 pii;#define MAX 300050int 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<work();return 0;
}