小苯的序列分割1.0

"""
【题目核心解析】
根据代码逻辑，题目的核心目标可以转化为：
将数组划分为 m 个连续的子段，使得其中所有「偶数编号子段」的元素和最大。
（最终答案 = 整个数组的总和 + 偶数段的最大元素和。这意味着奇数段元素被计算了1次，偶数段元素被计算了2次）

【动态规划模型建模】
1. 状态定义：
   理论上需要二维数组 f[i][j]，表示前 i 个元素被划分为 j 个连续子段时，偶数段元素和的最大值。
   为了优化空间，代码中使用了一维滚动数组 f[j] 来替代，倒序遍历 j 以保证状态正确转移。

2. 状态转移（分类讨论）：
   对于当前遍历到的第 i 个元素 a[i]，假设它被划分到了第 j 个子段中，它只有两种合法来源：
   - a[i] 作为第 j 段的第一个元素。继承自前 i-1 个元素分成 j-1 段的状态（即 f[j-1]）。
   - a[i] 追加到已有的第 j 段中。继承自前 i-1 个元素分成 j 段的状态（即当前的 f[j]）。

3. 依据 j 的奇偶性，进行具体的转移：
   3.1 若 j 为奇数（当前元素处于奇数段，不产生额外贡献）：
       不需要加上 a[i]。
       转移方程：f[j] = max(f[j], f[j - 1])

   3.2 若 j 为偶数（当前元素处于偶数段，需要计算额外贡献）：
       无论 a[i] 是新开一段还是追加同段，它的值都要累加到偶数段的总和中。
       转移方程：f[j] = max(f[j], f[j - 1]) + a[i]

4. 边界条件与遍历细节：
   - 初始化：f[0] = 0，其余为极小值（-1e18），表示除了“0个元素分0段”合法外，其余均为非法状态。
   - 倒序遍历：内层循环 j 必须倒序遍历（类似 0-1 背包的空间优化），以确保更新 f[j] 时，使用的 f[j-1] 是上一个元素（i-1）的历史状态，防止数据被提前污染。

5. 结果汇总：
   遍历完成后，f[m] 即为所有划分方案中，偶数段元素和的最大值。
   最终答案 ans = sum(A) + f[m]。
"""
t = int(input())

for _ in range(t):
    line = list(map(int, input().split()))
    n, m = line[0], line[1]
    a = list(map(int, input().split()))
    ans = sum(a)
    f = [-1e18] * (m + 1)
    f[0] = 0
    for i in range(n):
        for j in range(min(m, i + 1), 0, -1):
            if j % 2 == 0:
                f[j] = max(f[j], f[j - 1]) + a[i]
            else:
                f[j] = max(f[j], f[j - 1])
    print(ans + f[m])

import sys

T=int(input())
for t in range(T):
    n,m=list(map(int,input().strip().split()))
    a=list(map(int,input().strip().split()))
    if n==1 and m==1:
        print(a[0])
    else:
       
        dp=[[-float("inf")]*(1+m) for _ in range(1+n)]
        dp[0][0]=0
        presum=[0]*(n+1)
        for i in range(n):
            presum[i+1]=presum[i]+a[i]

        
        for i in range(1,n+1):
            
            for j in range(1,m+1):
                weight=1 if j%2 else 2
                best=-float("inf")
                for k in range(i):
                    best=max(best,dp[k][j-1]+(presum[i]-presum[k])*weight)
                dp[i][j]=best
        print(dp[n][m])




超时了

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            long[] a = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = sc.nextLong();
            }

            // 前缀和
            long[] prefix = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                prefix[i] = prefix[i - 1] + a[i];
            }

            // dp[i][j] 表示前 i 个数划分为 j 段的最大值
            long[][] dp = new long[n + 1][m + 1];
            for (int i = 0; i <= n; i++) {
                Arrays.fill(dp[i], Long.MIN_VALUE / 2);
            }
            dp[0][0] = 0;

            // 动态规划
            for (int j = 1; j <= m; j++) {
                int weight = (j % 2 == 1 ? 1 : 2);

                // best[k] = max(dp[k][j-1] - prefix[k]*weight)
                long best = Long.MIN_VALUE / 2;

                for (int i = 1; i <= n; i++) {
                    // 先更新 best (相当于枚举k=i-1)
                    best = Math.max(best, dp[i - 1][j - 1] - prefix[i - 1] * weight);

                    // 再利用 best 转移到 dp[i][j]
                    dp[i][j] = prefix[i] * weight + best;
                }
            }

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