题面：

题目描述

给定一个长度为 n 的序列 v[1..n]，现在要将这个序列分成 k 段（每段都不能为空），定义每一段的权值为该段上的所有数的或和。定义整个序列的权值为每段权值的和。问：这个序列的最大权值为多少。

输入格式

第一行两个数 n 和 k，意义如题意所示。 第二行 n 个数，表示这个序列 v[1..n]。

输出格式

输出一个数，代表这个序列的最大权值。

样例 #1

样例输入 #1

5 2
7 5 8 2 3

样例输出 #1

22

提示

对于 30%的数据，n <= 10, k <= 10 对于 60%的数据，n <= 100, k <= 100 对于 100%的数据，k <= n <= 2000，1 <= v[i] <= 5 * 10^5

---

我的80pts代码

#include <bits/stdc++.h>
#define N 2001
using namespace std;
int sum[N][N] , dp[N][N] , n , k ;
signed main() {
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin >> n >> k ;
    for(int i = 1 ; i <= n ; ++i ) cin >> sum[i][i];
    for(int i = 1 ; i <= n ; ++i ) 
        for(int j = i + 1 ; j <= n ; ++j ) 
            sum[i][j] = sum[i][j-1] | sum[j][j] ;
    for(int i = 1 ; i <= n ; ++i ) dp[i][1] = dp[i-1][1] | sum[i][i];   
    for (int i = 1 ; i <= n ; ++i ) {
        for(int j = 2 ; j <= k && j <= i ; ++j ) {
            for(int m = 1 ; m < i ; ++m ) 
                dp[i][j] = max(dp[i][j] , dp[m][j - 1] + sum[m+1][i]);
        }
    }
    cout << dp[n][k] <<"\n";
}