2000ms

Difficulty: 7

所属公司 : 小红书

时间 :2025年8月24日（算法岗）

算法与标签>动态规划

会员专享

请先登录，开通会员或购买该题目所属题库（小红书机考编程题库），可解锁完整内容。

购买题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（小红书机考编程题库），可解锁完整内容。

购买题库开通会员

思路概述

关键想法

若最后一段以位置 $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$ 个军团，满足:

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