A16503. Minimise Cost
编程题
NOI/NOI+/CTSC
知识点
题目描述
对于任意长度为 $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$ 的子序列。
$$ 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$。
第一行包含两个整数 $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
6 3 2 1 3 -2 3 1 1 3 -2 10 4 -4 -6 -8 6 -3 -7 -3 1 6 -5 10 9 1 -2 6 -2 -6 4 3 3 7 -1 20 5 -5 9 -4 10 -2 4 -1 3 5 6 7 9 8 1 0 -6 4 5 8 9 50 26 7 10 10 2 2 1 7 4 4 8 5 8 -10 6 1 4 7 8 0 0 -8 1 1 5 0 0 6 0 7 4 6 0 7 4 -2 0 0 8 1 4 -7 0 6 -9 4 10 8 2 0 9
输出 #1
1 6 -239 5 131 -404
说明/提示
在第一个测试点，将序列划分为 $[1,-2]$ 和 $[3]$ 最优。总分为 $2(1-2)+1(3)=1$。
在第二个测试点，只能采用一种划分方式，即一个子序列 $[1,3,-2]$。分数为 $3(1+3-2)=6$。
在第二个测试点，只能采用一种划分方式，即一个子序列 $[1,3,-2]$。分数为 $3(1+3-2)=6$。