Entopia's Memory Boost
InterviewTime limit1sMemory limit1024 MB
On a fixed 3x4 board with two thumbs that move one at a time, press a given sequence of cells minimizing movement plus press costs A and B.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Array, Implementation, Math
- Solved
- No attempts yet
Problem
Entopia is going to play a game to boost her memory.
As shown in the figure above, there is a game board with one integer in each of its 3×4 cells. Entopia is given a sheet of paper with the order in which the cells must be pressed. After 3 seconds, a monkey snatches the paper away. Now Entopia must remember it well and press the integers in order.
She presses the integers on the board with her left thumb or right thumb. Both the left thumb and the right thumb may rest on the same cell at the same time. However, she cannot move both fingers at the same time.
Entopia spends stamina both when she moves a finger and when she presses an integer. Moving a thumb from one cell to another costs stamina equal to the distance between the two cells. The distance between two cells is defined as the east-west distance plus the north-south distance. Pressing a cell with the left thumb costs A stamina, and pressing it with the right thumb costs B stamina.
Initially, the left thumb is on cell 1 and the right thumb is on cell 3. Given the order in which the integers must be pressed, find the minimum stamina Entopia uses.
Input
The first line gives three integers N, A, and B. The second line gives N integers, which represent the order in which the integers must be pressed.
Output
Print the minimum stamina used to finish the game.
Constraints
- 1 ≤ N ≤ 10,000
- 1 ≤ A, B ≤ 100
- The order contains only integers that exist on the game board.