3420. [统一省选 2020]信号传递

注意空间复杂度！

【题目描述】

  一条道路上从左至右排列着$m$个信号站，初始时从左至右依次编号为$1,2,\cdots ,m$，相邻信号站之间相隔 1 单位长度。每个信号站只能往它右侧的任意信号站传输信号（称为普通传递），每单位长度距离需要消耗 1 单位时间。

  道路的最左侧有一个控制塔，它在最左侧信号站的左侧，与其相隔 1 单位长度。控制塔能与任意信号站进行双向信号传递（称为特殊传递），但每单位长度距离需要消耗$k$个单位时间。

  对于给定的长度为 $n$ 的信号传递序列 $S$，传递规则如下：

  1. 共$n-1$次信号传递，第 $i$ 次信号传递将把信号从$S_i$号信号站传递给$S_{i+1}$ 号。

  2. 若 $S_{i+1}$ 号信号站在$S_i$号右侧，则将使用普通传递方式，从$S_i$号直接传递给$S_{i+1}$号。

  3. 若 $S_{i+1}$ 号信号站在$S_i$号左侧，则将使用特殊传递方式，信号将从$S_i$号传递给控制塔，再由控制塔传递给$S_{i+1}$号。

  4. 若$S_i$=$S_{i+1}$ ，则信号无须传递。

  阿基作为大工程师，他能够任意多次交换任意两个信号站的位置，即他能够重排信号站的顺序，这样会使得 $S$ 消耗的传递时间改变。现在阿基想知道，在他重排信号站顺序后，$S$ 所消耗的传递时间最小能是多少。

【输入格式】

第一行三个整数 $n,m,k$，分别代表信号传递序列 $S$ 的长度，信号站个数，特殊传递单位长度距离的时间消耗。

第二行 $n$ 个整数，第 $i$ 个整数表示$S_i$ 。

【输出格式】

仅一行一个整数表示答案。

【样例1输入】

3 3 1

1 2 3

【样例1输出】

2

【样例1解释】

信号站顺序保持不变，两次使用普通传递方式，时间消耗为 1 + 1 = 2。

【样例2输入】

4 3 1

1 2 3 1

【样例2输出】

6

【样例2解释】

对于排列 1,2,3，传递时间为 1 + 1 + (3 ∗ 1 + 1 ∗ 1) = 6。

对于排列 1,3,2，传递时间为 2 + (3 ∗ 1 + 2 ∗ 1) + (2 ∗ 1 + 1 ∗ 1) = 10。

对于排列 2,1,3，传递时间为 (2 ∗ 1 + 1 ∗ 1) + 2 + (3 ∗ 1 + 2 ∗ 1) = 10。

对于排列 2,3,1，传递时间为 (3 ∗ 1 + 1 ∗ 1) + 1 + 1 = 6。

对于排列 3,1,2，传递时间为 1 + (3 ∗ 1 + 1 ∗ 1) + 1 = 6。

对于排列 3,2,1，传递时间为 (3 ∗ 1 + 2 ∗ 1) + (2 ∗ 1 + 1 ∗ 1) + 2 = 10。

【样例3】

大样例

【数据范围】

30% 的数据：$m ≤ 8，n ≤ 100$。

60% 的数据：$m ≤ 20$。

70% 的数据：$m ≤ 21$。

80% 的数据：$m ≤ 22$。

100% 的数据：$2 ≤ m ≤ 23，2 ≤ n ≤10^5，1 ≤ k ≤ 100，1 ≤ S_i ≤ m$。

【来源】

HAOI2020 Day2 Task1