传送门：QAQQAQ
题意：给你一个数组，把它分成若干段，每一段之和都不得大于M，求每一段最大值之和的最小值
思路：状态转移方程：$dp[i]=min(dp[j]+max(a[j+1,i]))(sum_{k=j+1}^{k<=i}<=m)$
有关DP的优化，主要就是要缩短找到决策的时间
我们分析确定$i,j$时的决策，容易知道$dp$数组是单调不递减的，所以要使该决策是最佳决策，要么是所能取的最小$j$值，要么把$j,j+1$隔开时，后面的$max$有所减少
所以只有两种情况是最佳决策：一是最头，二是该数为该数后缀的最大值，对于第二种情况的决策我们可以用递减的单调队列来维护
因为最优决策不一定在队头，所以我们再用priority_queue维护一个堆，并用是否在单调队列内判断堆中值是否合法
在代码实现方面，因为STL堆不支持修改，删除操作，所以我们用懒惰删除法。
堆中维护的答案会随着区间最大值的变化而变化，但是我们发现对于当前插入的a[i]队列中比他小的都已经弹出，不合法，会被更新的只有一个——队列中$a[i]$的前一个值，只有它的max变化（$j$后的最大值就是它在单调队列中的下一个$a[i]$值）
修改时，因为没法删除或修改，我们可以通过$bl$数组维护对于第$i$个切开最新的答案，再把最新答案插进去，这样当旧答案出来时不相等即为不合法，一删一插相当于修改
剩下的就是细节问题了（如循环最后插入$i$时的$max$取$a[i+1]$）
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <queue> #include <vector> #define mk make_pair using namespace std; typedef long long ll; typedef pair<ll,ll> pii; const int N=100200; const ll inf=(ll) 5e18; deque<pii> q;//a[i],id priority_queue<pii,vector<pii>,greater<pii> > Q;//value,id ll n,m,a[N],bl[N],dp[N]; int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); if(a[i]>m) {puts("-1"); return 0;} } ll now=0,left=1; for(int i=1;i<=n;i++) { now+=a[i]; while(now>m&&left<=i) now-=a[left],left++; while(!q.empty()&&q.front().second<left) { bl[q.front().second]=-1; q.pop_front(); } while(!q.empty()&&q.back().first<=a[i]) //empty在前，否则RE { bl[q.back().second]=-1; q.pop_back(); } if(!q.empty()) { pii pre=q.back(); bl[pre.second]=dp[pre.second]+a[i]; Q.push(mk(dp[pre.second]+a[i],pre.second));//删掉旧决策，插入新决策 } q.push_back(mk(a[i],i)); dp[i]=dp[left-1]+q.front().first;//也可以这一段全选，不割最大值 while(!Q.empty()) { pii tmp=Q.top(); if(bl[tmp.second]!=tmp.first) { Q.pop(); continue; } dp[i]=min(dp[i],tmp.first); break; } bl[i]=dp[i]+a[i+1]; Q.push(mk(dp[i]+a[i+1],i));//dp值加上切掉以后下一段的最大值，即单调队列中后一个a[i]值 } cout<<dp[n]<<endl; return 0; }