解题思路
考虑线性 dp。
首先如果存在 \(a_i>m\)，那肯定不满足条件，输出 \(-1\)。
设 \(f_i\) 表示前 \(i\) 个数分成若干段，然后每段最大数之和，其中每段内的整数之和不超过 \(m\)。
\(f_i\) 肯定是由 \(f_j\)（\(1\le j<i\)）转移过来的，也就是前 \(j\) 个数分好后再加上 \((j,i]\) 这一段，所以 \((j,i]\) 这一段需要满足 \(\sum\limits_{k=j+1}^{i}a_k\le m\)，所以 \(j\) 就可以从 \(i-1\) 到 \(1\) 倒序枚举。
继而有转移方程：
\[f_i=\min_{j=1}^{i-1}\left\{\left[\sum_{k=j+1}^ia_k\le m\right]\times\max_{k=j+1}^i\left\{a_k\right\}\right\} \]时间复杂度为 \(\mathcal{O}(n^2)\)，得分 \(24\text{pts}\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], f[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
memset(f, 0x3f, sizeof(f));
f[0] = 0, f[1] = a[1];
for(int i = 2; i <= n; i++) {
int maxi = -1, sum = 0;
for(int j = i - 1; j >= 1 && sum + a[j] <= m; j--) {
sum += a[j];
maxi = max(maxi, a[j + 1]);
f[i] = min(f[i], f[j] + maxi);
}
}
cout << f[n];
return 0;
}
接着讲正解，单调队列优化 dp。
区间和可以用前缀和处理。
注意到 \(j\) 最小的时候满足 \(\sum\limits_{k=j+1}^ia_k\le m\)，也就是说 \(\sum\limits_{k=j}^ia_k>m\)，这个数可以单独处理，而 \(t=\max\limits_{k=j+1}^i\left\{a_k\right\}\) 可以通过单调队列存一个单调递减的最大值数列，但因为最后答案 \(f_j+t\) 不具有单调性，所以需要再存一个小根堆，建议用 multiset，因为每次删除时优先队列不好删除。
时间复杂度为 \(\mathcal{O}(n\log_2n)\)。
AC 代码，请勿抄袭
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], sum[N], f[N];
deque<int> dq;
multiset<int> s;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
bool flag = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
flag |= (a[i] > m);
sum[i] = sum[i - 1] + a[i];
}
if(flag) { return cout << "-1", 0; }
int p = 0;
for(int i = 1; i <= n; i++) {
while(sum[i] - sum[p] > m) { ++p; }
while(!dq.empty() && dq.front() <= p) {
int tmp = dq.front();
dq.pop_front();
if(!dq.empty()) { s.erase(f[tmp] + a[dq.front()]); }
}
while(!dq.empty() && a[dq.back()] <= a[i]) {
int tmp = dq.back();
dq.pop_back();
if(!dq.empty()) { s.erase(f[dq.back()] + a[tmp]); }
}
int tmp = (!dq.empty() ? dq.back() : 0);
dq.push_back(i);
f[i] = f[p] + a[dq.front()];
if(dq.size() > 1) {
s.insert(f[tmp] + a[i]);
f[i] = min(f[i], *s.begin());
}
}
cout << f[n];
return 0;
}