CF1969C Minimizing the Sum

You are given an integer array $ a $ of length $ n $ . You can perform the following operation: choose an element of the array and replace it with any of its neighbor's value. For example, if $ a=[3, 1, 2] $ , you can get one of the arrays $ [3, 3, 2] $ , $ [3, 2, 2] $ and $ [1, 1, 2] $ using one operation, but not $ [2, 1, 2 $ \] or $ [3, 4, 2] $ . Your task is to calculate the minimum possible total sum of the array if you can perform the aforementioned operation at most $ k $ times.

N/A

N/A

In the first example, one of the possible sequences of operations is the following: $ [3, 1, 2] \rightarrow [1, 1, 2 $ \]. In the second example, you do not need to apply the operation. In the third example, one of the possible sequences of operations is the following: $ [2, 2, 1, 3] \rightarrow [2, 1, 1, 3] \rightarrow [2, 1, 1, 1] $ . In the fourth example, one of the possible sequences of operations is the following: $ [4, 1, 2, 2, 4, 3] \rightarrow [1, 1, 2, 2, 4, 3] \rightarrow [1, 1, 1, 2, 4, 3] \rightarrow [1, 1, 1, 2, 2, 3] $ .