Codeforces 981D(存在性DP+位运算性质)

Codeforces 981D
题意：给定$n$个数数列，求将数列分成$k$部分的和按位与的最大值。
最开始认为DP但是不符合子结构最优性质……
但是我们可以转化为存在性 DP，我们发现题目的所求答案不会大于$2^{50} \times 50$
根据位运算性质，我们贪心地，二进制下取高位一定是比取下所有低位的优的，所有我们要不遗余力地尽可能取高位，所以从高位开始枚举检验能不能取。可以用存在性DP来判。具体实现可以看代码实现

知识点：
1、所有 LL 数都加上 ll 后缀；
2、DP 要看满不满足子结构最优性质，不要上来就 DP，可以转成存在性 DP

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 55ll;

    LL now, n, k, a[MAXN], sum[MAXN][MAXN], dp[MAXN][MAXN];

    LL chk(LL x) {
        LL gg = now | (1ll << x); // 1ll!
        ms(dp, 0ll);
        for (LL i = 1ll; i <= n; ++i) if ((sum[1ll][i] & gg) == gg) dp[i][1ll] = 1ll;
        for (LL i = 1ll; i <= n; ++i) {
            for (LL j = 1ll; j <= i; ++j) {
                for (LL o = 1ll; o < i; ++o) {
                    if ((sum[i - o + 1ll][i] & gg) == gg) dp[i][j] |= dp[i - o][j - 1ll];
                }
            }
        }
        return dp[n][k];
    }

    void clean() {
    }
    int solve() {
        clean();
        cin >> n >> k;
        for (LL i = 1ll; i <= n; ++i) cin >> a[i];
        for (LL i = 1ll; i <= n; ++i) {
            sum[i][0ll] = 0ll;
            for (LL j = i; j <= n; ++j) sum[i][j] = sum[i][j - 1ll] + a[j];
        }
        now = 0ll;
        for (LL i = 55ll; i >= 0ll; --i) {
            if (chk(i)) now |= (1ll << i);
        }
        cout << now;
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}