题目描述
给定一个长度为 $n$ 的数列 $a_i$，将其划分为 $k$ 个连续的子段，每一段和相与的值最大是多少。
$1\le k\le n\le 50$，$0\lt a_i\le 2^{50}$。
算法分析
看到相与的值最大，考虑按位贪心，定义 $f_{i,j}$ 表示将前 $i$ 个数划分为 $j$ 段时能否满足前面所有位都为已经求出的最大值且当前枚举到的位为 $1$。
设当前正在判断的数为 $x$，则状态转移方程为 $f_{i,j}=f_{i,j}\bigcup (f_{k,j-1}\bigcap [((\sum\limits_{t=1}^ia_t-\sum\limits_{t=1}^ka_t)\bigcap x)=x])$。
时间复杂度为 $O(n^3)$。注意 $\sum a_t$ 的大小为 $50\times2^{50}$，因此需要枚举更多的位，同时 1<<x 默认是 int 所以要写成 1ULL<<x。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <cstdio>
#include <cstring>
#define N 55
typedef unsigned long long int ull;
int n,K;ull a[N];bool f[N][N];
inline bool check(ull x) {
memset(f,0,sizeof(f));f[0][0]=1;
for(register int i=1;i<=n;++i) {
for(register int j=1;j<=K;++j) {
for(register int k=0;k<i;++k) {
f[i][j]|=(f[k][j-1]&&(((a[i]-a[k])&x)==x));
}
}
}
return f[n][K];
}
int main() {
scanf("%d%d",&n,&K);
for(register int i=1;i<=n;++i) {scanf("%llu",a+i);a[i]+=a[i-1];}
ull ans=0;
for(register int i=63;i>=0;--i) if(check(ans|(1ULL<<i))) ans|=(1ULL<<i);
printf("%llu\n",ans);
return 0;
}
|