思路概述
关键想法
若最后一段以位置 i 结尾、上一段结尾在 t−1 处（即最后一段是 [t,i]），则该段贡献为
x∈[t,i]minax。
设 dp[j][i] 表示将前 i 个数分成 j 段的最大和，则有
P3471.第2题-贪心的小C
题目内容
小C在玩一个游戏。他手下有n名士兵，第i名士兵的能力值为ai。
他需要将这n名士兵划分成k个军团，满足:
- 军团间的士兵编号互不重叠;
- 军团内部士兵编号连续;
- 每个军团至少包含一个士兵。
对第j个军团，其战力值mj为该军团内能力最低的士兵能力值。
小C想要最大化所有军团战力值之和：S=∑j=1kmj
请你计算能够获得的最大总战力值S。
输入描述
第一行输入两个整数n和k(1≤k≤min(n,100),1≤n≤104),分别表示士兵数n和要划分的军团数k。
第二行输入n个整数a1,a2,...,an(1≤ai≤100),表示每名士兵的能力值。
输出描述
输出一个整数，表示将n名士兵划分成k个军团后，所有军团战力值之和的最大值。
样例1
输入
5 2
1 3 2 4 5
输出
6
说明
在第一个样例中:
最优划分为军团{1,3,2,4}和军团{5};
两个军团的最小能力值分别为1和5;
总能力值之和为1十5=6。
样例2
输入
5 3
5 1 2 4 3
输出
9
说明
在第二个样例中:
最优划分为军团{5},{1,2,4},{3};
三个军团的最小能力值分别为5,1,3;
总能力值之和为5+1+3=9。
