Bookshelves

Bookshelves

按位贪心然后dp去验证，实在是太妙了，，，

从高到底，如果高位能选的话优先选高位(低位所有的都选上还是比它小)，
接下来就是dp验证当前解是否可行了，定义dp[i][j]表示用前i本书放在前j个书架上是否可以得到当前答案满足要求。

然后不断更新合法答案即可，整体复杂度

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 55;

int n, k;

ll a[N];

bool f[N][N];

bool judge(ll x) {
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int r = 1; r <= n; r++) {
        for (int i = 1; i <= k; i++) {
            for (int l = 0; l < r; l++) {
                f[r][i] |= f[l][i - 1] & (((a[r] - a[l]) & x) == x);
            }
        }
    }
    return f[n][k];
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        a[i] += a[i - 1];
    }
    ll ans = 0;
    for (int i = 60; i >= 0; i--) {
        ll res = ans | 1ll << i;
        if (judge(res)) {
            ans = res;
        }
    }
    printf("%lld\n", ans);
    return 0;
}