這道題算是我做過所有的單調(diào)隊列優(yōu)化 $dp$ 題目中最難想的一道題，所以寫篇題解再捋捋思路。

暴力

首先很容易想到設(shè) $d{p}_i$ 表示將前 $i$ 個數(shù)劃分成若干序列，【每個序列的最大值之和】的最小值。
那么就會有：
$$\begin{gathered} d{p}_i=min\left\{\begin{array}{c}d{p}_j+ma{x}_{k=j+1}^i\left\{\begin{array}{c}{a}_k\end{array}\right\}\end{array}\right\}, \\ 其中0\le j<i且\sum _{k=j+1}^i{a}_k\le m. \end{gathered}$$
這樣子的復(fù)雜度是 $O(n^3)$，考慮優(yōu)化。

優(yōu)化

先證明一個東西，那就是 $d{p}_i$ 是單調(diào)不減的（也就是非嚴(yán)格單調(diào)遞增），即：對于任意的 $i$，都有 $d{p}_i\le d{p}_{i+1}$。
這是顯然的，因為多加一個數(shù)，它如果單開一個序列，那么就會造成貢獻；如果它歸為最后一個已有的序列，那么若它比最后一序列中的最大值小，那么它就不會產(chǎn)生貢獻，否則就會產(chǎn)生貢獻，使最大值之和變大。

然后觀察轉(zhuǎn)移方程：
$$d{p}_i=min\left\{\begin{array}{c}d{p}_j+ma{x}_{k=j+1}^i\left\{\begin{array}{c}{a}_k\end{array}\right\}\end{array}\right\}$$
可以發(fā)現(xiàn)，$ma{x}_{k=j+1}^i\left\{\begin{array}{c}{a}_k\end{array}\right\}$ 隨著 $j$ 的增加，是非嚴(yán)格單調(diào)遞減的，因為右端點 $i$ 不動，所以 $[j+1,i]$ 中的的最大值是越來越小或者不變的。
因此我們就會有一個這樣的發(fā)現(xiàn)：在 m a x k = j + 1 i { a k } max_{k = j + 1}^{i} \left \{ a_k \right\} maxk=j+1i?{ak?} 的值相等的情況下，我的決策點 $j$ 是越靠前越好的（因為 $d{p}_i$ 是單調(diào)不減的嘛）。
如此一來，在合法區(qū)間內(nèi)有若干個的可能的最優(yōu)決策點（分別對應(yīng)使 m a x k = j + 1 i { a k } max_{k = j + 1}^{i} \left \{ a_k \right\} maxk=j+1i?{ak?} 值相等的最小的位置 $j$）。因此我們就用單調(diào)隊列來維護 $a_k$ 單調(diào)遞減，隊列所記錄的位置就是一個可能的決策點。
至于查詢所有可能決策點的最小貢獻，用 $multiset$ 來實現(xiàn)（這句可能不好理解，可以先看代碼）。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 7;int n, a[maxn];
ll m, s, dp[maxn];
int l[maxn];
int q[maxn], h, t;
multiset<ll> S;
int main() {scanf("%d%lld", &n, &m);for (int i = 1; i <= n; ++i) {scanf("%d", a + i);if (a[i] > m) {printf("-1\n");return 0;}}// 預(yù)處理使 a[j+1...i] 之和小于等于 m 的最小 jfor (int i = 1, j = 0; i <= n; ++i) {s += a[i];while (s > m) s -= a[++j];l[i] = j;} h = 1, t = 0;for (int i = 1; i <= n; ++i) {// 如果之前的某些決策點已經(jīng)不在合法區(qū)間// 那么就要刪去, 其所對應(yīng)的可能答案也要刪去while (h <= t && q[h] < l[i]) {S.erase(dp[q[h]] + a[q[h + 1]]);++h;}// 維 a 護單調(diào)遞減while (h <= t && a[q[t]] <= a[i]) {S.erase(dp[q[t - 1]] + a[q[t]]);--t;}if (h <= t) S.insert(dp[q[t]] + a[i]);q[++t] = i;// 這句是為了包括【隊頭的決策點】【從合法區(qū)間的最左端轉(zhuǎn)移過來】的情況// 學(xué)校機房上傳不了圖片來解釋，先鴿著dp[i] = dp[l[i]] + a[q[h]];  if (S.size()) dp[i] = min(dp[i], *(S.begin()));}printf("%lld\n", dp[n]);return 0;
}