Line Empire

题意翻译

你是一个野心勃勃的帝王，但在你征服实数集的王国前，你需要先征服整数集的王国。 假设有一个数轴，你的王国以及其首都初始均位于原点。除此之外数轴上还有 $n$ 个未被征服的王国，它们分别位于整数 $x_1,x_2,\cdots,x_n$ 处。你的目标即是征服这些王国。 给定常数 $a,b$，你可以进行下列操作若干次： - 你可以选择一个已经被征服的王国，然后把首都迁到那个王国。 假设你的首都与所选王国距离为 $c$，那么这次操作的代价为 $a\times c$。 - 你可以选择一个没有被征服的王国，**满足你的首都与其之间没有其他未被征服的王国**，然后征服那个王国。 假设你的首都与所选王国距离为 $c$，那么这次操作的代价为 $b\times c$。 求出征服所有王国的最小总代价。 每个测试点包含 $T$ 组数据。 保证： $1\leq T\leq10^3;$ $1\leq n,\sum n\leq2\times10^5;1\leq a,b\leq10^5;$ $1\leq x_i\leq10^8$ 且 $x$ 单调递增。

题目描述

You are an ambitious king who wants to be the Emperor of The Reals. But to do that, you must first become Emperor of The Integers. Consider a number axis. The capital of your empire is initially at $ 0 $ . There are $ n $ unconquered kingdoms at positions $ 0<x_1<x_2<\ldots<x_n $ . You want to conquer all other kingdoms. There are two actions available to you: - You can change the location of your capital (let its current position be $ c_1 $ ) to any other conquered kingdom (let its position be $ c_2 $ ) at a cost of $ a\cdot |c_1-c_2| $ . - From the current capital (let its current position be $ c_1 $ ) you can conquer an unconquered kingdom (let its position be $ c_2 $ ) at a cost of $ b\cdot |c_1-c_2| $ . You cannot conquer a kingdom if there is an unconquered kingdom between the target and your capital. Note that you cannot place the capital at a point without a kingdom. In other words, at any point, your capital can only be at $ 0 $ or one of $ x_1,x_2,\ldots,x_n $ . Also note that conquering a kingdom does not change the position of your capital. Find the minimum total cost to conquer all kingdoms. Your capital can be anywhere at the end.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The description of each test case follows. The first line of each test case contains $ 3 $ integers $ n $ , $ a $ , and $ b $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ; $ 1 \leq a,b \leq 10^5 $ ). The second line of each test case contains $ n $ integers $ x_1, x_2, \ldots, x_n $ ( $ 1 \leq x_1 < x_2 < \ldots < x_n \leq 10^8 $ ). The sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output a single integer — the minimum cost to conquer all kingdoms.

输入输出样例

输入样例 #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

说明

Here is an optimal sequence of moves for the second test case: 1. Conquer the kingdom at position $ 1 $ with cost $ 3\cdot(1-0)=3 $ . 2. Move the capital to the kingdom at position $ 1 $ with cost $ 6\cdot(1-0)=6 $ . 3. Conquer the kingdom at position $ 5 $ with cost $ 3\cdot(5-1)=12 $ . 4. Move the capital to the kingdom at position $ 5 $ with cost $ 6\cdot(5-1)=24 $ . 5. Conquer the kingdom at position $ 6 $ with cost $ 3\cdot(6-5)=3 $ . 6. Conquer the kingdom at position $ 21 $ with cost $ 3\cdot(21-5)=48 $ . 7. Conquer the kingdom at position $ 30 $ with cost $ 3\cdot(30-5)=75 $ . The total cost is $ 3+6+12+24+3+48+75=171 $ . You cannot get a lower cost than this.