poj3017 Cut the Sequence

单调队列+treap
会爆栈,要c++扩栈。
题意:给出n个数(n<=10^5),给出m,要求将数列分成连续的若干段,使得每段之和<=m,且每段中的最大值的和最小,求这个最小的和
分析:
很容易得到:dp[i]=min{dp[j]+max{a[j+1……i]}|bound[i]<=j<=i-1},其中bound[i]是使得sigma(a[j+1]……a[i])<=m的最大下标,可以二分得到。
状态数O(n),转移O(n),显然要优化。
由于bound[i]是随着i的增大单调不降的,而且一个点j要成为i的最优决策首先必须满足a[j]比a[j+1……i]都要大(这点还不明白)。那么我们可以用单调队列维护。
现在对于确定的决策j,我们可以O(1)时间知道a[j+1]~a[i]的最大值(若q[p]=a[j],那么max{a[j+1]~a[i]}=q[p+1],q[p+1]存在的前提下),但是对于状态i,当前单调队列的队首元素的原始下标不一定就是最优决策值,所以我们要找到一种数据结构动态的维护dp[j]+max{a[j+1]~a[i]},其中a[j]是当前单调队列中的元素。那么显然当状态转移的时候需要对这种数据结构插入、删除、求最小值。显然这种数据结构应当是平衡树为好。
思路还是很清晰的,但是要注意细节,队列中的元素个数要时刻清晰,插入删除了哪些决策下的答案要清楚。还有就是对于决策是bound这种情况,要特判。因为我代码里面的单调队列都是从bound+1开始的元素。