Binary Search on Lambda

Define $f(\lambda)$ = number of segments in the optimal answer when penalty is $\lambda$. This function is monotonic: larger $\lambda$ means fewer segments.

Binary search (halving the search range each step) on $\lambda$ to find where $f(\lambda) = K$. At that penalty, the optimal solution happens to use exactly $K$ segments. The answer is: (penalized cost at optimal $\lambda$) $- K \times \lambda$. You subtract the penalty to get the true cost.