2024.3.31 腾讯笔试第四题

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    long[][] dp = new long[k + 1][n + 1];

    for (int i = 0; i < n; i++) {
        dp[1][i + 1] = in.nextInt() ^ dp[1][i];
    }

    long[] prefix = dp[1];
    // 拆分为 i 份
    for (int i = 2; i <= k; i++) {
        // 从头到尾遍历：将第 1~j 个元素拆成 i 份
        for (int j = i; j <= n; j++) {
            long max = 0;
            // 将第 [1,s] 个元素拆成 i-1 份，(s,j] 是最后一份
            for (int s = j - 1; s >= i - 1; s--) {
                // 异或的优先级小于加减法
                max = Math.max(max, dp[i - 1][s] + (prefix[j] ^ prefix[s]));
            }
            dp[i][j] = max;
        }
    }

    System.out.println(dp[k][n]);
}