3700. [APIO2014]序列分割

【题目描述】

你正在玩一个关于长度为$n$的非负整数序列的游戏。这个游戏中你需要把序列分成$k+1$个非空的块。为了得到$k+1$块，你需要重复下面的操作$k$次：

选择一个有超过一个元素的块（初始时你只有一块，即整个序列）

选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

【输入格式】

第一行包含两个整数$n$和$k$。保证$k+1≤n$。

第二行包含$n$个非负整数$a_1,a_2,…,a_n(0<=a_i<=10^4)$，表示前文所述的序列。

【输出格式】

输出你能获得的最大总得分。

【样例输入】

7 3
4 1 3 4 0 2 3

【样例输出】

108

【样例说明】

你可以通过下面这些操作获得$108$分： 

初始时你有一块$(4,1,3,4,0,2,3)$。在第$1$个元素后面分开，获得$4×(1+3+4+0+2+3)=52$分。 

你现在有两块$(4), (1, 3, 4, 0, 2, 3)$。在第$3$个元素后面分开，获得$(1+3)×(4+0+2+3)=36$分。 

你现在有三块$(4), (1, 3), (4, 0, 2, 3)$。在第$5$个元素后面分开，获得$(4+0)×(2+3)=20$分。 

所以，经过这些操作后你可以获得四块$(4), (1, 3), (4, 0), (2, 3)$并获得$52+36+20=108$分。

【数据规模与约定】

前$40\%$,$1≤k<n≤200$

$2≤n≤100000,1≤k≤min\{n−1,200\}$

【来源】

APIO2014，有适当更改