解题思路
本题要求将 N 个关卡恰好划分为 K 个非空连续阶段，每个阶段的得分为该阶段内所有关卡得分之和。总得分为：第 1,3,5,…（奇数编号）阶段的得分按原值累加，第 2,4,6,…（偶数编号）阶段的得分按两倍累加。求最大可能的总得分。
- 定义 前缀和 prefix[i]=∑t=1iat，用于快速计算任意区间的得分和。
- 设计 动态规划：
- 令 dp[i][j] 表示将前 i 个关卡划分成 j 个阶段时，能够获得的最大总得分。
- 边界条件：dp[0][0]=0，其余状态初始化为负无穷。
- 第 j 个阶段的权值 wj 为：若 j 为奇数，wj=1；若 j 为偶数，wj=2。
题目内容
在一个游戏中，有 N 个连续关卡，每个关卡有一个得分（可能为负数）。玩家需要将这些关卡恰好划分为 K 个连续的非空阶段，每个阶段的总分构成序列 S1,S2,…,SK。计算总得分时，奇数编号的阶段（第 1,3,5,… 个阶段）按原分数值累加，偶数编号的阶段（第 2,4,6,… 个阶段）按原分数值的两倍累加。求所有划分方案中，可能获得的最大总得分。
本题包含多组测试数据，所有数据满足以下约束：
- 测试数据组数 T 满足 1≤T≤100。
- 每组数据中，关卡数量 N 和阶段数 K 满足 1≤K≤N≤3000。
- 所有测试数据的 N 之和不超过 3000。
- 每个关卡的得分 ai 满足 ∣ai∣≤109。
输入描述
