DDOSvoid's Blog

CF 981D Bookshelves

发表于 分类于
本文字数： 753 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/981/D

Solution

从高位到低位贪心，每次算上之前能够得到的值一起做 $dp$ 判断即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#define maxn 110
#define ll long long
using namespace std;

int n, m;

ll a[maxn], s[maxn];

bool f[maxn][maxn];
bool check(ll x) {
    fill(f[0], f[0] + maxn * maxn, 0); f[0][0] = 1; 
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int k = 0; k < i; ++k)
                if ((s[i] - s[k] & x) == x) f[i][j] |= f[k][j - 1]; 
    return f[n][m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i - 1] + a[i];
    ll ans = 0; 
    for (int i = 60; ~i; --i) 
        if (check(ans | 1ll << i)) ans |= 1ll << i;
    cout << ans << "\n"; 
    return 0;
}