【每日一题】Bookshelves 题解(dp, bitmasks)

Description

给出n个数字，要求分成k个连续的子数组，使得每一堆总和按位与的结果是最大的

Solution

思路：dp + 贪心，首先意识到要结果最大需要按位贪心，从高位往低位取。其次，关于某一位是否能够实现，可以用 dp 去解决。具体实现如下：
令bool 变量 dp[i][d] 表示到第i个数字的时候已经分为d个连续子数组时，该二进制位是否能实现按位and后仍然为1.那么有
后面那一坨表示从j + 1 到 i 的前缀和在该二进制位上是否为1。
注意：题目给的 , 但是前缀和不一定在这个范围，需要多检测几位(第60位开始即可)，不然会wrong answer

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll a[65];
bool dp[65][65];
int n, k; 
bool solve(ll x) {
  memset(dp, false, sizeof(dp));
  dp[0][0] = true;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < i; j++) {
      for(int d = 1; d <= k; d++) {
        dp[i][d] |= (dp[j][d - 1] & (((a[i] - a[j]) & x) == x));
      }
    }
  }
  return dp[n][k];
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  cin >> n >> k;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] = a[i - 1] + a[i];
  }
  ll ans = 0, res = 0;
  for(ll i = 60; i >= 0; --i) {
    res = (ans | (1LL << i));
    if(solve(res)) {
      ans = res;
    }
  }
  cout << ans << '\n';
  return 0;
}