思路概述

关键想法

若最后一段以位置 $i$ 结尾、上一段结尾在 $t-1$ 处（即最后一段是 $[t,i]$），则该段贡献为 $\min\limits_{x\in[t,i]} a_x$。 设 $dp[j][i]$ 表示将前 $i$ 个数分成 $j$ 段的最大和，则有

题目内容

小C在玩一个游戏。他手下有$n$名士兵，第$i$名士兵的能力值为$a_i$。

他需要将这$n$名士兵划分成$k$个军团，满足:

• 军团间的士兵编号互不重叠;
• 军团内部士兵编号连续;
• 每个军团至少包含一个士兵。