Hello.
I have a problem and I don't know how to solve it. if it is possible to give me hint for start or type of algorithm, etc, I will solve it. Thanks.
We have array $$$A$$$ with $$$n$$$ elements: A[1], A[2], A[3], ..., A[n] (1 <= A[i] <= 10) (n <= 1000)
A $$$k$$$ is given beside elements of array. (0 <= k <= 10 * n)
We define risk = 0.
for each $$$i$$$, if $$$A[i - 1] > A[i]$$$, then $$$risk += A[i - 1] - A[i]$$$
for each $$$i$$$, if $$$A[i + 1] > A[i]$$$, then $$$risk += A[i + 1] - A[i]$$$
we want to $$$risk <= k$$$.
we can reduce or increase A[i] at each step. What is minimum steps need to achieve $$$risk <= k$$$?
Example:
in:
2 1
1 10
out:
8
in:
3 2
10 1 10
out:
8
Is it possible to help me? Thanks so much.