CF1866J.Jackets and Packets

Pak Chanek has $N$ jackets that are stored in a wardrobe. Pak Chanek's wardrobe has enough room for two stacks of jackets, namely the left stack and the right stack. Initially, all $N$ jackets are in the left stack, while the right stack is empty. Initially, the $i$-th jacket from the top of the left stack has colour $C_i$.

Pak Chanek wants to pack all of those jackets into some packets, such that the jackets in the same packet has the same colour. However, it is possible for two jackets with the same colour to be in different packets.

Pak Chanek can do two kinds of operations:

• Pak Chanek can pick any number of jackets from the top from one stack as long as the colour is the same, then take those jackets out of the stack and pack them into a packet. This packing operation takes $X$ minutes, no matter how many jackets are packed.
• Pak Chanek can move one topmost jacket from one stack to the top of the other stack (possibly right to left or left to right). This moving operation takes $Y$ minutes.

Determine the minimum time to pack all jackets!

帕克·查内克有 $N$ 件夹克，存放在一个衣柜中。该衣柜恰好能容纳两叠夹克：左叠和右叠。初始时，全部 $N$ 件夹克均位于左叠中，而右叠为空。初始时，左叠从上往下第 $i$ 件夹克的颜色为 $C_i$。

帕克·查内克希望将所有这些夹克装入若干个包裹中，使得每个包裹内的夹克颜色相同。但允许颜色相同的两件夹克被装入不同的包裹。

帕克·查内克可以执行以下两类操作：

• 从某一叠的顶部取出任意数量的夹克（要求这些夹克颜色相同），将其从该叠中移除并装入一个包裹。此打包操作耗时恒为 $X$ 分钟，与打包夹克的数量无关。
• 将某一叠最顶端的一件夹克移动至另一叠的顶端（可从左叠移至右叠，也可从右叠移至左叠）。此移动操作耗时 $Y$ 分钟。

求将所有夹克全部打包所需的最少时间！

The first line contains three integers $N$, $X$, and $Y$ ($1 \leq N \leq 400$; $1\leq X,Y\leq10^9$) — the number of jackets, the time to do a packing operation, and the time to do a movement operation.

The second line contains $N$ integers $C_1, C_2, C_3, \ldots, C_N$ ($1 \leq C_i \leq N$) — the colour of each jacket.

第一行包含三个整数 $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$）—— 表示每件夹克的颜色。

An integer representing the minimum time to pack all jackets.

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

Let's denote the contents of the two stacks using arrays that represent the colours of the jackets in the stack from top to bottom. Initially, the two stacks form $[4, 4, 2, 4, 1, 2, 2, 1]$ and $[]$.

Pak Chanek can do the following sequence of operations:

1. Movement from left to right. The two stacks become $[4, 2, 4, 1, 2, 2, 1]$ and $[4]$.
2. Movement from left to right. The two stacks become $[2, 4, 1, 2, 2, 1]$ and $[4, 4]$.
3. Packing for $1$ jacket from the top of the left stack. The two stacks become $[4, 1, 2, 2, 1]$ and $[4, 4]$.
4. Movement from left to right. The two stacks become $[1, 2, 2, 1]$ and $[4, 4, 4]$.
5. Movement from left to right. The two stacks become $[2, 2, 1]$ and $[1, 4, 4, 4]$.
6. Packing for $2$ jackets from the top of the left stack. The two stacks become $[1]$ and $[1, 4, 4, 4]$.
7. Movement from right to left. The two stacks become $[1, 1]$ and $[4, 4, 4]$.
8. Packing for $3$ jackets from the top of the right stack. The two stacks become $[1, 1]$ and $[]$.
9. Packing for $2$ jackets from the top of the left stack. The two stacks become $[]$ and $[]$.

In total, it requires a time of $2+2+7+2+2+7+2+7+7=38$ minutes to pack all jackets. It can be proven that there are no other ways that are faster.

我们用两个数组来表示两个栈的内容，数组中元素从上到下依次为夹克的颜色。初始时，两个栈分别为 $[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$ 分钟完成全部夹克的打包。可以证明，不存在更快的方案。