思路概述

关键想法

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

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

对第$j$个军团，其战力值$m_j$为该军团内能力最低的士兵能力值。

小$C$想要最大化所有军团战力值之和：$S=\sum ^k_{j=1}m_j$

请你计算能够获得的最大总战力值$S$。

输入描述

第一行输入两个整数$n$和$k(1≤k≤min(n,100),1≤n≤10^4)$,分别表示士兵数$n$和要划分的军团数$k$。

第二行输入$n$个整数$a_1,a_2,...,a_n$$(1≤a_i≤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$。