考虑朴素\(dp\)，设\(dp_i\)表示前\(i\)个数划分后的最小答案
可以得到转移：
\[dp_i = \min_{j=1}^{i-1}\{dp_j + \max_{k=j+1}^{i}\{a_k \} \}
\]
计算复杂度\(O(n^2)\)，会超时
我们发现对于可能成为答案的状态是以下条件的一个：
-
\(\sum_{k=j}^{i} a_k > M\)
-
\(\max_{k=j}^{i}\{a_k\} = a_j\)
第一个限制没什么好说的，第二个限制的原因是\(dp_i\)单调不降，对于\(\max\)的值相同的部分，我们肯定是取更靠前的更优
因此我们对\(a_i\)维护单调递减的单调队列，这里单调队列表示的是可能成为答案的部分，而不是直接维护答案
对于在单调队列里的元素，我们用一个堆来维护\(dp_j + \max_{k=j+1}^{i}\{a_k \}\)的值。当单调队列里的某个元素删掉时，这个堆也删掉这个元素；同理，当单调队列中被加入元素时也加入
但这里有一个问题：\(dp_j + \max_{k=j+1}^{i}\{a_k \}\)中\(i\)的右端点是会向后移动来影响答案的，但我们无法做到实时更新\(\max\)的值
但我们假设在加入元素\(i\)后单调队列里的值为：\(q_1,q_2,...,q_t,i\)，我们发现此时会影响的答案只有\(q_t\)，因此我们只需要把\(q_t\)在堆中的答案删掉后加入新的即可
堆的具体实现可以使用\(multiset\)
最终复杂度\(O(n \log n)\)，复杂度瓶颈在于堆