Shortest paths - interesting graph problems
In older games, which have 2D graphics, one can run into the next situation. The hero jumps along the platforms or islands that hang in the air. He must move himself from one side of the screen to the other. The hero can jump from any platform number i to any platform number k, spending (i - k) * (i - k) * (
yk) * (
yk) energy, where
yk are the heights where these platforms hang. Obviously energy should be spent frugally.
You are given the heights of the platforms in order from the left side to the right. Can you find the minimum amount of energy to get from the 1-st (start) platform to the n-th (last)?
The first line contains the number of platforms n (1 ≤ n ≤ 4000). The second line gives n integers - the heights of the platforms, which absolute values are not greater than 200000.
Print the singe integer which is the minimum amount of energy to get from the 1-st platform to the n-th.
4 1 2 3 30