CF1768F Wonderful Jump

You are given an array of positive integers $ a_1,a_2,\ldots,a_n $ of length $ n $ . In one operation you can jump from index $ i $ to index $ j $ ( $ 1 \le i \le j \le n $ ) by paying $ \min(a_i, a_{i + 1}, \ldots, a_j) \cdot (j - i)^2 $ eris. For all $ k $ from $ 1 $ to $ n $ , find the minimum number of eris needed to get from index $ 1 $ to index $ k $ .

N/A

N/A

In the first example: - From $ 1 $ to $ 1 $ : the cost is $ 0 $ , - From $ 1 $ to $ 2 $ : $ 1 \rightarrow 2 $ — the cost is $ \min(2, 1) \cdot (2 - 1) ^ 2=1 $ , - From $ 1 $ to $ 3 $ : $ 1 \rightarrow 2 \rightarrow 3 $ — the cost is $ \min(2, 1) \cdot (2 - 1) ^ 2 + \min(1, 3) \cdot (3 - 2) ^ 2 = 1 + 1 = 2 $ . In the fourth example from $ 1 $ to $ 4 $ : $ 1 \rightarrow 3 \rightarrow 4 $ — the cost is $ \min(1, 4, 4) \cdot (3 - 1) ^ 2 + \min(4, 4) \cdot (4 - 3) ^ 2 = 4 + 4 = 8 $ .