AcWing
299. 裁剪序列
DP：定义$f[i]$：前$i$个元素的所有划分方式中最大值和的最小值。当$i=n$时，$f[n]$即为所求。任取序列$a[1, i]$的最后一段$j\sim i$，假设最大长度为$k$，则有$j\in[i-k+1, i]$，$f[i] = \min_j{{f[j - 1] + a_{max}[j, i]}}$. 这样，迭代$i$, $j$, $\max_ja[j]$，总体的时间复杂度是$O(n^3)$. 下面考虑优化：
在从右到左迭代$j$的同时，可以同时取得$\max_ja[j]$，优化到$O(n^2)$；注意到在$j\in[i-k+1, i]$时，$f[j]$具有单调性，而$a_{max}[j, i]$具有离散性，所以考虑在区间$[i - k + 1, i]$维护一个单调队列（单调递减）$[k_1, k_2, k_3, \cdots ]$，$k_1 + f[k - 1]$与$k_2 + f[k_1]$， $k_3 + f[k_2]$，$\cdots$，$k_N + f[k_{N - 1}]$共同构成了$f[i]$所有可能的最小值，使用multiset来维护（因为可能有相同大小的值），其底层基于红黑树实现，使得修改的效率为$O(logn)$；再加上区间维护（双指针）$O(n)$的时间复杂度，算法总体的时间复杂度减小到$O(nlogn)$.
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, a[N], q[N]; // q存单调队列中的值在a中的下标
multiset<long long> res;
long long m, f[N];
void rmv(long long x){
auto it = res.find(x);
res.erase(it);
}
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];
if(a[i] > m){
cout << -1 << endl;
return 0;
}
}
int hh = 1, tt = 0, k = 1;
long long sm = 0;
for(int i = 1; i <= n; i++){
sm += a[i];
while(hh <= tt && a[i] >= a[q[tt]]){
if(hh < tt) rmv(f[q[tt - 1]] + a[q[tt]]);
tt--;
}
q[++tt] = i;
if(hh < tt) res.insert(f[q[tt - 1]] + a[q[tt]]);
while(sm > m){
sm -= a[k];
k++;
}
while(hh <= tt && q[hh] < k){
if(hh < tt) rmv(f[q[hh]] + a[q[hh + 1]]);
hh++;
}
f[i] = f[k - 1] + a[q[hh]];
if(!res.empty()) f[i] = min(f[i], *res.begin());
}
cout << f[n] << '\n';
return 0;
}