Codeforces 674C Levels and Regions - Aliens Trick

Add penalty $\lambda$ per region. Penalized DP: $dp_{\lambda}[i]$ = min cost to partition first $i$ levels into any number of regions, with penalty. Transition: $dp_{\lambda}[i] = \min_{p < i}(dp_{\lambda}[p] + cost(p+1, i) + \lambda)$. The $+\lambda$ is the per-region penalty.

Now you have $O(n)$ states (one per position). If $cost(l, r)$ can be computed in $O(1)$ with preprocessing, total time is $O(n^2)$ per binary search iteration, or $O(n^2 \log C)$ overall.