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;
}

------ 本文结束 ------