Dynamic Programming - Linear
Journey from west to east
There are n cities standing on a straight line from west to east. The cities are numbered from 1 to n, in order from west to east. Each point on the line has its own one-dimensional coordinate, and the point closer to the east has a large coordinate. The coordinate of the i-th city is
You are now in city 1, and want to visit all cities. You have two ways to travel:
- Walk in a straight line. At the same time, your level of fatigue will increase by a units each time you move a distance of 1, regardless of the direction.
- Teleport to any point you want. Your fatigue level will increase by b units, regardless of teleported distance.
First line contains three numbers n (2 ≤ n ≤
105), a and b (1 ≤ a, b ≤
109). Next line contains n integers
x2, ... ,
xn (1 ≤
109). For all i (1 ≤ i ≤ n – 1) holds inequality
Print the lowest possible level of fatigue, at which you will visit all the cities.
From city 1 we go to 2-nd, then teleport to 3-rd. Then go to 4-th. The level of fatigue at the end will be equal to 2 * 1 + 5 + 2 * 2 = 11, what is the lowest possible.
From city 1 you simply go to all others till the 7-th. As a result, the level of fatigue will be equal to 84, which is the lowest possible.
Visit all cities, in any order, teleporting six times. The level of fatigue will be equal to 12, which is the lowest possible.
4 2 5 1 2 5 7
6 3 7 1 3 6 10 11 13
7 1 2 24 35 40 68 72 99 103