POJ 3017 单调队列+最值优化 的动态规划
令f[i] 表示前i个数按照题目要求的最小的和
则必然有f[i] = min(f[j] + max(a[j +1 , a[j + 2].....a[i]))
其中j<= i,j的位置还得满足题目中m 的限制
由于a数组都是大于0的，所以可以发现f必然是非递减的。
设a[j + 1], a[j + 2], ...a[i]中值最大的下标为k
设x为[j + 1,k]的任意一个下标，则a[x],a[x+1],....a[i]的最大值的下标显然也是k了
由f的非递减性，f[j+1] + a[k] <= f[j+2]+a[k].....<= f[k - 1] + a[k]
很显然，我们只要取f[j+1]+a[k]就可以了。
也就是说如果某一段到当前i位置的最大值都一样，取最靠前的即可。
如何维护呢，可以联想到单调队列。
维护一个递减的队列，存的是符合要求的某一段的最大值，但是可以发现，并不是队首元素就是最优，因为队列中的递减性质，队列中的所有元素都有可能导致最优解。
这时可以用到的东西就很多了，堆啊，各种树这样的。实际上，用个set可以有效的减少代码量。
具体代码见http://www.cnblogs.com/yymore/archive/2011/06/27/2091748.html
不过30多行就解决问题了。
