分数: 1000 点
问题陈述
给你一个排列 p = (p_1, \ldots, p_N) of \{ 1, \ldots, N \}。 您可以按任意顺序重复执行以下两种操作:
- 支付费用 A。选择整数 l 和 r (1 \leq l < r \leq N),并移位 (p_l, \ldots, p_r) 向左移动一位。也就是说,替换 p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r 与 p_{l + 1}, p_{l + 2}, \ldots, p_r, p_l。
- 支付费用 B。选择整数 l 和 r (1 \leq l < r \leq N),并移位 (p_l, \ldots, p_r) 向右移动一位。 也就是说,替换 p_l, p_{l + 1}, \ldots, p_{r - 1}, p_r 与 p_r, p_l, \ldots, p_{r - 2}, p_{r - 1}。
找出排序所需的最小总成本 p 按升序排列。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 5000
- 1 \leq A, B \leq 10^9
- (p_1 \ldots, p_N) 是一个排列 \{ 1, \ldots, N \}.
输入
输入由标准输入按以下格式给出:
N A B p_1 \cdots p_N
输出
打印排序所需的最低总成本 p 按升序排列。
示例输入 1
3 20 30 3 1 2
示例输出 1
20
换档 (p_1, p_2, p_3) 向左移 1 结果为 p = (1, 2, 3).
示例输入 2
4 20 30 4 2 3 1
示例输出 2
50
一种可能的操作顺序如下:
- 转变 (p_1, p_2, p_3, p_4) 向左移动一位。现在我们有 p = (2, 3, 1, 4).
- 转变 (p_1, p_2, p_3) 向右移动一位。现在我们有 p = (1, 2, 3, 4).
这里,总成本是 20 + 30 = 50.
示例输入 3
1 10 10 1
示例输出 3
0
示例输入 4
4 1000000000 1000000000 4 3 2 1
示例输出 4
3000000000
示例输入 5
9 40 50 5 3 4 7 6 1 2 9 8
示例输出 5
220