Binary search the minimum danger factor ~D~ that requires ~K~ or fewer operations to enforce.

Instead of finding the minimum number of hills that must be adjusted, find the maximum number of hills that can be left alone. The height difference between each consecutive hill is at most ~D~. So if hill ~i~ and hill ~j~ are both unadjusted, ~|h[i]-h[j]| \le D(i-j)~.

Partial Solution

Let ~dp[i]=~ the maximum number of unadjusted hills up to hill ~i~, assuming you don't adjust hill ~i~. Let ~j~ be the last hill before ~i~ that was unadjusted. ~dp[i]=\max(dp[j])+1~ for all ~|h[i]-h[j]| \le D(i-j)~. In total there can be ~\max_{1 \le i \le N} dp[i]~ unadjusted hills. This gives an ~\mathcal O(N^2 \log 10^9)~ solution, which doesn't give any points on DMOJ because this subtask doesn't exist.

Full Solution

The condition ~|h[i]-h[j]| \le D(i-j)~ can be converted to ~h[i]-h[j] \le D(i-j), h[j]-h[i] \le D(i-j)~, so you are trying to find the longest sequence of hills ~a_1, a_2, \dots~ such that ~Da_i-h[a_i] \le Da_{i+1}-h[a_{i+1}]~ and ~Da_i+h[a_i] \le Da_{i+1}+h[a_{i+1}]~. This is equivalent to finding the longest nondecreasing subsequence over pairs ~(Di-h[i],Di+h[i])~ for ~1 \le i \le N~ which results in an ~\mathcal O(N \log N \log 10^9)~ solution.