CFCF2183H.Minimise Cost

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

对于任意长度为 $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

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,-2]$ 和 $[3]$ 最优。总分为 $2(1-2)+1(3)=1$ 。

在第二个测试点，只能采用一种划分方式，即一个子序列 $[1,3,-2]$ 。分数为 $3(1+3-2)=6$ 。

首页