3017 -- Cut the Sequence

3017 -- Cut the Sequence

Given an integer sequence { a_n } of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.

Input

The first line of input contains two integer N (0 < N ≤ 100 000), M. The following line contains N integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.

Output

Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output −1.

Sample Input

8 17  

2 2 2 8 1 8 2 1

Sample Output

12

Hint

Use 64-bit integer type to hold M.

长度为 n 的数列，要求把这个数列划分为任意块，每块的元素和小于 m，使得所有块的最大值的和最小。

https://pan.baidu.com/s/1gexnMwj

刚开始拿到这道题目，首先要读好题：最大值的和最小。

首先设计出一个动态规划的方法：

https://sea96.github.io/2017/02/25/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%9A%84%E5%90%84%E7%A7%8D%E4%BC%98%E5%8C%96/

题意：给定一个有$n$个非负整数的数列$a(a_i\le {10}^5)$，要求将其划分为若干个部分，使得每部分的和不超过给定的常数$m$，并且所有部分的最大值的和最小。

题解：朴素的动态规划的算法：定义$dp\left[i\right]$表示前$i$个数字划分后所有部分最大值的和，$m(l,r)$表示区间$[l,r]$的最大值，$sum(l,r)$表示区间$[l,r]$的和，状态转移方程：
$$dp\left[i\right]=min\left\{dp\left[t\right]+m(t+1,i)\right\},sum(t+1,i)\le m$$
因为是非负整数，dp的值显然是递增的，但是并没有可维护单调的序列，决策点也没有单调性，需要挖掘出单调性，引用kuangbin的做法：

首先假如不考虑m的限制，那么最优决策的$j$点，一定满足$a\left[j\right]>max\left(a\right[j+1i\left]\right)$就是$j$点的值要大于$j+1$到$j$点的值。
很明显的结论，因为假如不成立，那么可以把$j$点也划分到后面去，得到更优的
所以用单调队列维护一个递减数列，这样的话最优决策点只能出现在这些点中。
现在加了$m$的限制，假如上面那个递减数列只有后面一部分是满足$m$限制的。
那么决策点就是上面这些点再加上满足$m$条件的那个边界，所以可以用平衡二叉树维护二叉树里面的值只要随着队列进行维护就好了，可以用multiset实现。

Read full article from 3017 -- Cut the Sequence