题目描述

难度分:$1900$

输入$n$，$k(1 \leq k \leq n \leq 50)$和长为$n$的数组$a(0 \lt a[i] \lt 2^{50})$。

把$a$划分成恰好$k$个非空连续子数组。

把第$i$个子数组记作$b[i]$。

最大化$sum(b[0])$AND$sum(b[1])$AND$…$AND$sum(b[k-1])$。

这里AND表示按位与。

输入样例$1$

10 4
9 14 28 1 7 13 15 29 2 31

输出样例$1$

24

输入样例$2$

7 3
3 14 15 92 65 35 89

输出样例$2$

64

算法

按位贪心+动态规划

这个题目没有办法直接用划分型DP来做，因为这个AND运算会破坏动态规划的无后效性。但是这种带位运算的题目我们可以自然而然地想到按位贪心，从高到低来考虑每个二进制位。对于第$m$位，我们进行划分型DP。

状态定义

$f[i][j]$表示将子数组$[1,i]$划分成$j$个非空段，是否能保证每个非空段的累加和按位与后在第$m$位为$1$。

状态转移

最外层循环枚举将数组划分成的段数$k$，然后考虑将子数组$[1,r]$划分为$k$段，找到最后一段的范围$(l,r]$。状态转移方程为：

$f[r][k]=f[l][k-1] \land (target \land \Sigma_{i=l+1}^{r}a[i]=target)$

其中只要有一个$l$能够保证$f[r][k]$为true就说明$f[r][k]$可以为true。求和操作可以通过预处理出$a$的前缀和数组来加速计算，只要$f[n][k]$是true，说明最终结果在第$m$位可以是$1$。

多位约束技巧

当然，还存在一个问题，就是在第$m$位是$1$的情况下，是有可能让高位的某个$1$变成$0$的。这时候让当前位变成$1$就得不偿失了，于是就需要状态转移中的$target$参数，用来保证当前第$m$位仍然受到之前高位的影响。$target$中为$1$的二进制位，就是迄今为止能保证最终答案为$1$的所有二进制位。

复杂度分析

时间复杂度

遍历所有二进制为的时间复杂度可以看成是$O(log_2A)$，其中$A$是$a$数组中的最大数，可以用$\Sigma_{i=1}^{n}a[i]$来近似。本题中$log_2A$最大就是$51$位，二进制位数多几个少几个对答案的影响很小。对于每个二进制位，需要对$a$进行划分型DP，时间复杂度为$O(n^3)$。

综上，整个算法的时间复杂度为$O(n^3log_2A)$。

空间复杂度

前缀和数组可以直接在输入的数组$a$上求，从而省下这个空间消耗。因此算法的额外空间复杂度就是DP数组$f$的消耗，即$O(n^2)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 55;
int n, K, f[N][N];
LL s[N];

int getLen(LL x) {
    int len = 0;
    while(x) {
        len++;
        x >>= 1;
    }
    return len;
}

int main() {
    scanf("%d%d", &n, &K);
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }
    LL ans = 0;
    for(int b = getLen(s[n]); b >= 0; b--) {
        memset(f, 0, sizeof(f));
        LL bit = 1ll << b, target = ans | bit;
        for(int i = 1; i <= n; i++) {
            f[i][1] = (s[i]&target) == target? 1: 0;
        }
        for(int k = 2; k <= K; k++) {
            for(int r = 1; r <= n; r++) {
                for(int l = 1; l < r; l++) {
                    LL range_sum = s[r] - s[l];
                    f[r][k] |= f[l][k - 1] & ((range_sum&target) == target? 1: 0);
                }
            }
        }
        if(f[n][K]) ans = target;
    }
    printf("%lld\n", ans);
    return 0;
}