Jackets and Packets
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2800
Tags: dp

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!

Input format:
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.

Output format:
An integer representing the minimum time to pack all jackets.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
8 7 2
4 4 2 4 1 2 2 1

Example output:
38

Editorial:
Instead of looking at the two stacks as two separate arrays, consider them as a single array $$$A$$$ whose elements are the colours of the jackets in the right stack from bottom to top, then the colours of the jackets in the left stack from top to bottom. Also maintain a pointer that indicates the separation point between the right and left stack parts of the the array (the pointer is located at the gap between two adjacent elements instead of at an element). So, $$$A$$$ is initially equal to $$$C$$$ with the pointer located directly to the left of the leftmost element.
Notice that a movement operation is equivalent to moving the pointer one step to the left or right. A packing operation is equivalent to erasing a contiguous group of elements of the same value directly to the left or to the right of the pointer.
We can solve this problem using dynamic programming. Define the following values:
• $$$\text{dp}[l][r]$$$: the minimum time to erase all elements if the array is $$$A[l..r]$$$ and the pointer is located directly to the left of the leftmost element.
Now, consider the two transition cases for $$$\text{dp}[l][r]$$$.
If $$$A_l$$$ does not get erased in the same operation as $$$A_r$$$, then optimally, there must be a prefix of $$$A[l..r]$$$ (let's say it is $$$A[l..p]$$$) that gets entirely erased before doing anything with the rest of $$$A[l..r]$$$. For a particular partition of prefix, we must solve for that prefix, then solve for the rest. So to calculate for this case, we must find the minimum of all values of $$$\text{dp}[l][p]+\text{dp}[p+1][r]$$$.
If $$$A_l$$$ gets erased in the same operation as $$$A_r$$$ (can only happen when $$$A_l=A_r$$$), then there must be a set of disjoint segments entirely within segment $$$[l,r]$$$ where every single one of those segment gets entirely erased before the one single packing operation that simultaneously erases $$$A_l$$$ and $$$A_r$$$. It must hold that every element outside of the segments has the same value as $$$A_l$$$ and $$$A_r$$$.
For the case above, notice that in the optimal way, we repeatedly iterate the pointer directly to the left of each segment and completely erase the segment before going for the next segment. After all that, we can choose to move the pointer either directly to the left of $$$A_l$$$ or to the right of $$$A_r$$$, then erase the rest of $$$A[l..r]$$$ in one packing operation.
To handle this, we define two new DP values for the case where $$$A_l$$$ and $$$A_r$$$ get erased in the same operation:
• $$$\text{dpA}[l][r]$$$: the minimum time for this case if after erasing the last segment, the pointer moves to the right of $$$A_r$$$.
• $$$\text{dpB}[l][r]$$$: the minimum time for this case if after erasing the last segment, the pointer moves to the left of $$$A_l$$$.
The transitions for $$$\text{dpA}$$$ are:
• If all elements of $$$A[l..r]$$$ have the same value, then $$$\text{dpA}[l][r]=Y\times(r-l+1)+X$$$ (the pointer moves to the very right, then erases all elements).
• Else, then we check every possible index $$$p$$$ for the next index in $$$A[l..r]$$$ not in the set of segments after $$$l$$$. So $$$\text{dpA}[l][r]$$$ is the minimum of $$$Y+\text{dpA}[l+1][r]$$$ and all values of $$$Y+\text{dp}[l+1][p-1]+\text{dpA}[p][r]$$$ for all $$$A_p=A_l$$$ (the pointer moves one step to the right, then solves $$$A[l+1..p-1]$$$, then continues to solve the rest of $$$A[l..r]$$$ knowing that $$$A_l$$$ will get erased along with $$$A_r$$$ in the end).
The transitions for $$$\text{dpB}$$$ are:
• If all elements of $$$A[l..r]$$$ have the same value, then $$$\text{dpB}[l][r]=X$$$ (the pointer moves to the very left, then erases all elements).
• Else, then we check every possible index $$$p$$$ for the next index in $$$A[l..r]$$$ not in the set of segments after $$$l$$$. So $$$\text{dpB}[l][r]$$$ is the minimum of $$$Y\times2+\text{dpB}[l+1][r]$$$ and all values of $$$Y\times2+\text{dp}[l+1][p-1]+\text{dpB}[p][r]$$$ for all $$$A_p=A_l$$$ (the pointer moves one step to the right, then solves $$$A[l+1..p-1]$$$, then continues to solve the rest of $$$A[l..r]$$$, then moves the pointer all the way to the left passing through $$$A_l$$$ once again, before erasing the initial $$$A_l$$$ and $$$A_r$$$ in one packing operation).
Time complexity: $$$O(N^3)$$$