王钦石の二分

Train2012-sol-wqs
奇怪,这么多年居然从没听说过这个东西!
求将n个元素的数组分成k段的最优化分类的问题。
比如,n个元素的数组划分为k段,最小化平方和,那就二分一个常数C,求最小化\sum s_i^2+C需要分成几段。显然,随着C的增大,最优的段数是单调不下降的,就可以找到分为k段的C,然后答案-kC就是最终的答案。