← 返回题目列表

Codeforces · 1659/C

C. 线帝国

中文机器翻译题面 查看原题

你是一位雄心勃勃的国王,想成为皇族的皇帝。但要做到这一点,你必须首先成为整数皇帝。

考虑一个数轴。你的帝国的首都最初是$$$0$$$。在位置 $$$0<x_1<x_2<\ldots<x_n$$$ 处有 $$$n$$$ 未征服的王国。你想征服所有其他王国。

您可以执行两项操作:

- 你可以将你的首都位置(假设其当前位置为$$$c_1$$$)更改为任何其他被征服的王国(假设其位置为$$$c_2$$$),成本为$$$a\cdot |c_1-c_2|$$$。
- 从当前首都(假设其当前位置为$$$c_1$$$),你可以征服一个未征服的王国(假设其位置为$$$c_2$$$),成本为$$$b\cdot |c_1-c_2|$$$。如果目标和你的首都之间有一个未被征服的王国,你就无法征服一个王国。

请注意,您不能将首都放置在没有王国的地方。换句话说,在任何时候,您的资本只能是 $$$0$$$ 或 $$$x_1,x_2,\ldots,x_n$$$ 之一。另请注意,征服一个王国不会改变首都的位置。

找出征服所有王国的最低总成本。你的资本可以在最后的任何地方。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。每个测试用例的描述如下。

每个测试用例的第一行包含 $$$3$$$ 整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq a,b \leq 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_1 < x_2 < \ldots < x_n \leq 10^8$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 征服所有王国的最低成本。

示例

输入 #1

4
5 2 7
3 5 12 13 21
5 6 3
1 5 6 21 30
2 9 3
10 15
11 27182 31415
16 18 33 98 874 989 4848 20458 34365 38117 72030

输出 #1

173
171
75
3298918744

注意

这是第二个测试用例的最佳移动顺序:

1. 征服位于$$$1$$$的王国,成本为$$$3\cdot(1-0)=3$$$。
2.将首都迁至位置$$$1$$$的王国,成本为$$$6\cdot(1-0)=6$$$。
3. 征服位于$$$5$$$的王国,成本$$$3\cdot(5-1)=12$$$。
4. 将首都迁至位置$$$5$$$的王国,成本$$$6\cdot(5-1)=24$$$。
5. 征服位于$$$6$$$的王国,成本为$$$3\cdot(6-5)=3$$$。
6. 征服位于$$$21$$$的王国,成本$$$3\cdot(21-5)=48$$$。
7. 征服位于$$$30$$$的王国,成本$$$3\cdot(30-5)=75$$$。

总成本为$$$3+6+12+24+3+48+75=171$$$。您无法获得比这更低的成本。