3.31 腾讯笔试第四题66% 求大佬指点

小红拿到了一个数组，她准备将数组分割成 k 段，使得每段内部按位异或后，再全部求和。小红希望最终这个和尽可能大，你能帮帮她吗？

输入描述

输入包含两行。第一行两个正整数 n, k （$$ 1 \leq k \leq n \leq 400$$ ），分别表示数组的长度和要分的段数。

第二行 n 个整数 $$ a_i $$ （ $$0 \leq a_i \leq 10^9$$），表示数组 a 的元素。

输出描述

输出一个正整数，表示最终的最大和。

示例1

输入

6 2

1 1 1 2 3 4

输出

10

import java.util.Scanner;

public class Demo84 {
    // 动态规划 f[i][cnt] 表示[i, n-1]分割 k-cnt 段能产生的最大和 return f[0][0]
    // 初始化最后一排为0，最后一列为0 内外层都是从后往前遍历
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n];
        int[] sum = new int[n + 1]; // 异或前缀和
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            sum[i + 1] = sum[i] ^ arr[i];
        }
        long[][] f = new long[n + 1][k + 1];
        for (int i = k - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                for (int t = n; t >= j + 1 ; t--) { // 状态转移
                    f[i][j] = Math.max(f[i][j], f[i + 1][t] + (sum[t] ^ sum[j]));
                }
            }
        }
        System.out.println(f[0][0]);
    }
}