← 返回题目列表

AtCoder · agc032_d

D. 旋转排序

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

分数: 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