When computing , you need to track two things: the optimal cost and how many segments (or items) produced that cost. Store pairs: (cost, count). During DP transitions (moving from one state to the next), when you have a tie in cost, you need a tie-breaking rule.
If you're binary searching for the where count equals , prefer fewer segments when searching upward and more segments when searching downward. The count tells you , which drives your binary search. Without accurate counts, you can't find the right penalty.