CF1866J Jackets and Packets

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 \leq 10^9$），分别表示夹克的数量、一次打包操作所需的时间和一次移动操作所需的时间。 第二行包含 $N$ 个整数 $C_1, C_2, \ldots, C_N$（$1 \leq C_i \leq N$），表示每件夹克的颜色。

输出一个整数，表示将所有夹克全部打包所需的最少时间。

我们用数组表示两个堆中夹克的颜色，从上到下排列。最开始，两个堆分别为 $[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$ 分钟来打包所有夹克。可以证明没有更快的方法。 由 ChatGPT 4.1 翻译