CF2183H Minimise Cost

对于任意长度为 $m$ 的序列 $b$，我们定义其代价函数 $f(b)$ 为： $$ f(b) = m \cdot \sum_{i=1}^m b_i。 $$ 现给定一个长度为 $n$ 的序列 $a$ 和一个整数 $k$。 你的任务是将序列 $a$ 划分为恰好 $k$ 个非空子序列 $^\ast$，记为 $s_1, s_2, \ldots, s_k$，使得原序列 $a$ 的每一个元素都属于且只属于其中一个子序列。 请你求出总代价的最小可能值，即 $$ \sum_{i=1}^k f(s_i)。 $$ $^\ast$ 如果序列 $c$ 可以通过从序列 $d$ 删除若干（可以为零个或全部）任意位置的元素得到，则称 $c$ 是 $d$ 的子序列。

每个测试点包含多组测试数据。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。每组测试数据描述如下。 第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 2 \cdot 10^5$），分别表示给定序列的长度和需要划分的子序列数。 第二行包含 $n$ 个整数 $a_1,a_2, \ldots, a_n$（$\mathbf{-10^9} \le a_i \le \mathbf{10^9}$），表示序列 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示所有子序列代价之和的最小值。

在第一个测试点，将序列划分为 $[1,-2]$ 和 $[3]$ 最优。总分为 $2(1-2)+1(3)=1$。 在第二个测试点，只能采用一种划分方式，即一个子序列 $[1,3,-2]$。分数为 $3(1+3-2)=6$。 由 ChatGPT 5 翻译