← 返回题目列表

Codeforces · 1866/J

J. 夹克和包

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

Pak Chanek 有 $$$N$$$ 夹克,存放在衣柜里。 Pak Chanek 的衣柜有足够的空间容纳两叠夹克,即左叠和右叠。最初,所有 $$$N$$$ 夹克都在左侧堆栈中,而右侧堆栈为空。最初,左堆栈顶部的第 $$$i$$$ 夹克的颜色为 $$$C_i$$$。

Pak Chanek 希望将所有这些夹克打包到一些包中,以便同一包中的夹克具有相同的颜色。但是,两件颜色相同的夹克可能会装在不同的包装中。

Pak Chanek 可以执行两种操作:

- Pak Chanek 可以从一堆夹克的顶部挑选任意数量的夹克,只要颜色相同,然后将这些夹克从一堆夹克中取出并打包成一个包。无论包装多少件夹克,此包装操作都需要 $$$X$$$ 分钟。
- Pak Chanek 可以将一件最上面的夹克从一堆移动到另一堆的顶部(可能从右到左或从左到右)。此移动操作需要 $$$Y$$$ 分钟。

确定打包所有夹克的最短时间!

输入

第一行包含三个整数 $$$N$$$、$$$X$$$ 和 $$$Y$$$ ($$$1 \leq N \leq 400$$$; $$$1\leq X,Y\leq10^9$$$) — 夹克的数量、执行打包操作的时间和执行移动操作的时间。

第二行包含 $$$N$$$ 整数 $$$C_1, C_2, C_3, \ldots, C_N$$$ ($$$1 \leq C_i \leq N$$$) — 每件夹克的颜色。

输出

一个整数,表示打包所有夹克的最短时间。

示例

输入 #1

8 7 2
4 4 2 4 1 2 2 1

输出 #1

38

注意

让我们使用数组来表示两个堆栈的内容,这些数组从上到下表示堆栈中夹克的颜色。最初,两个堆栈形成 $$$[4, 4, 2, 4, 1, 2, 2, 1]$$$ 和 $$$[]$$$。

Pak Chanek 可以执行以下操作序列:

1. 从左向右移动。两个堆栈变成$$$[4, 2, 4, 1, 2, 2, 1]$$$ 和$$$[4]$$$。
2. 从左向右移动。两个堆栈变为 $$$[2, 4, 1, 2, 2, 1]$$$ 和 $$$[4, 4]$$$。
3. 从左叠顶部开始包装 $$$1$$$ 夹克。这两个堆栈变为 $$$[4, 1, 2, 2, 1]$$$ 和 $$$[4, 4]$$$。
4. 从左向右移动。这两个堆栈变为 $$$[1, 2, 2, 1]$$$ 和 $$$[4, 4, 4]$$$。
5. 从左向右移动。这两个堆栈变为 $$$[2, 2, 1]$$$ 和 $$$[1, 4, 4, 4]$$$。
6. 从左堆顶部开始包装 $$$2$$$ 夹克。这两个堆栈变为 $$$[1]$$$ 和 $$$[1, 4, 4, 4]$$$。
7. 从右向左移动。这两个堆栈变为 $$$[1, 1]$$$ 和 $$$[4, 4, 4]$$$。
8. 从右侧堆栈的顶部包装 $$$3$$$ 夹克。这两个堆栈变为 $$$[1, 1]$$$ 和 $$$[]$$$。
9. 从左堆顶部开始包装 $$$2$$$ 夹克。这两个堆栈变成$$$[]$$$ 和$$$[]$$$。

打包所有夹克总共需要 $$$2+2+7+2+2+7+2+7+7=38$$$ 分钟的时间。可以证明没有其他方法更快。