Problem1256--最小特征值之和

1256: 最小特征值之和

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 191  Solved: 79
[Submit] [Status] [Web Board] [Creator:]

Description

给定一个长度为 n 的数组 A 和一个整数 c,A 的特征值为前个小的元素之外的元素的和。比如A={3, 1, 6, 5, 2}, c = 2,那么 A 的特征值就为 3+5+6=14。 现要求将 A 划分为若干个子数组,使得所有子数组的特征值之和最小,输出最小的特征值之和。

Input

首先输入两个整数 n,c (1<=n,c<=1e6)
接下来输入n个数字,代表数组A (0<=ai<=1e9)

Output

输入最小特征值之和。

Sample Input

7 2
2 3 6 4 5 7 1

Sample Output

17

HINT

对于 2 3 6 4 5 7 1 可以划分为 2 3,6 4 5 7,1,那么结果就是 3 + 6 + 7 + 1 = 17
感谢太傅同学提供的原始题面,来源: https://acm.taifua.com/archives/csu-summer-camp-2020.html