Super platforms#8577
In many classic 2D games, you might encounter a scenario where a hero jumps across platforms (or islands) suspended in the air. The goal is to move from one side of the screen to the other. When the hero jumps from one platform to the next, he expends energy equal to |y_2 - y_1|, where y_2 and y_1 are the heights of the respective platforms. Additionally, the hero has a special move that allows him to skip a platform, costing 3 \cdot |y_2 - y_1| energy units. The number of times this special move can be used is limited, ranging from k_{min} to k_{max} times (inclusive). Naturally, the hero should aim to minimize energy expenditure.
Given the heights of all platforms from left to right and the constraints on the number of special moves, can you determine the minimum energy required for the hero to travel from the first platform to the last?
The first line contains the number of platforms (1 \leq n \leq 10000). The second line lists natural numbers, each not exceeding , representing the heights of the platforms. The third line provides two non-negative integers k_{min} and k_{max} (0 \leq k_{min} \leq k_{max} \leq \frac{n-1}{2}).
Output a single number — the minimum energy the hero must spend to traverse the platforms (assuming no cheat codes are used).
Esempio 1
Esempio 2
Esempio 3
Esempio 4
1) It's optimal to jump without using the special move (using it times).
2) The hero must use the special move exactly once, with no alternative but to jump directly from the first platform to the last.
3) It's beneficial to use one special move to leap from the first platform to the last.
4) There are effectively no special moves available (amount = ), so the hero must jump sequentially through each platform.