A16669 | $Cyclic Merging$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，这些数排成一个环。对于每个 $1\le i< n$，$a_i$ 与 $a_{i+1}$ 相邻；$a_1$ 与 $a_n$ 也相邻。 你需要恰好进行 $n-1$ 次如下操作： - 每次选择环上任意一对相邻的元素，记它们的值分别为 $x$ 和 $y$，将它们合并为一个值为 $\max(x,y)$ 的元素，花费为 $\max(x,y)$。 注意，每次操作会使环的长度减少 $1$，相邻关系也会随之更新。 请计算将环合并为一个元素的最小总花费。

每组测试数据包含多组测试用例。第一行为测试用例数 $t$，满足 $1 \le t \le 10^4$。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含一个整数 $n$，$2\le n\le 2\cdot 10^5$。 接下来一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，满足 $0\le a_i \le 10^9$。 保证所有测试用例中 $n$ 之和不超过 $2\cdot 10^5$。

对于每组测试用例，输出一个整数，表示将环合并为一个元素所需的最小总花费。

输入 #1

3
4
1 1 3 2
2
0 2
7
1 1 4 5 1 4 1

输出 #1

6
2
19

C++ 编辑器

输入

输出