程序员灯塔 天道酬勤关注互联网+大数据相关技术.
给你 n个点，问分成 1∼n 组，每一组的代价就是这一组中的最大值，问每一种情况的最小权值和。
把状态定义为 d i j 表示 走到 i 号点了 分了j 组的最小代价。
那么先枚举分成了几组 ，枚举从哪个点转移。
这样的暴力的复杂度是 n^3的，考虑怎么优化。
首先 max(1 ~ j)这个肯定是单调递增的，然后如果碰到一个比较大的点，比前面的都大的情况的话，最优的转移肯定是找到前面 (d[k][j-1])的最小值，因为当前的所有的额外权值是固定的，所以前面的这个越小，总价值就越小。所以用单调栈维护一个 权值 递增的单调栈，也就是 后面这个max 的这一半，同时维护一个单调栈中弹出来的最小的 dp 值，也就是说 如果一个大权值放到栈里面，弹出来这些值可以也可以作为转移的点。同时还需要维护一个当前 dp 的值，用于判断 当前这个点 要不要新开一个新的组。