P3648 [APIO2014] 序列分割

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块，你需要重复下面的操作 $k$ 次： 选择一个有超过一个元素的块（初始时你只有一块，即整个序列） 选择两个相邻元素把这个块从中间分开，得到两个非空的块。 每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

无

无

你可以通过下面这些操作获得 $108$ 分： 初始时你有一块 $(4, 1, 3, 4, 0, 2, 3)$。在第 $1$ 个元素后面分开，获得 $4 \times (1 + 3 + 4 + 0 + 2 + 3) = 52$ 分。 你现在有两块 $(4), (1, 3, 4, 0, 2, 3)$。在第 $3$ 个元素后面分开，获得 $(1 + 3) \times (4 + 0 + 2 + 3) = 36$ 分。 你现在有三块 $(4), (1, 3), (4, 0, 2, 3)$。在第 $5$ 个元素后面分开，获得 $(4 + 0) \times (2 + 3) = 20$ 分。 所以，经过这些操作后你可以获得四块 $(4), (1, 3), (4, 0), (2, 3)$ 并获得 $52 + 36 + 20 = 108$ 分。 限制与约定 第一个子任务共 11 分，满足 $1 \leq k < n \leq 10$。 第二个子任务共 11 分，满足 $1 \leq k < n \leq 50$。 第三个子任务共 11 分，满足 $1 \leq k < n \leq 200$。 第四个子任务共 17 分，满足 $2 \leq n \leq 1000, 1 \leq k \leq \min\{n - 1, 200\}$。 第五个子任务共 21 分，满足 $2 \leq n \leq 10000, 1 \leq k \leq \min\{n - 1, 200\}$。 第六个子任务共 29 分，满足 $2 \leq n \leq 100000, 1 \leq k \leq \min\{n - 1, 200\}$。 感谢@larryzhong 提供的加强数据