出题方案
现在小泽的手上有 (n) 道难题，编号分别为 (1sim n) ，第 (i) 道题的难度系数是 (a_i) 。
小泽想用这些题出比赛，他会把题目按照编号划分为若干个非空连续区间，每个区间对应了一场比赛。
特别的，如果某场比赛的题目难度系数之和超过了给定的常数 (m) ，这场比赛会过于毒瘤，所以他不希望出现这样的情况。
定义每场比赛的难度系数为这场比赛所有题目难度系数的最大值。
小泽想让你找出一组合法方案，使得所有比赛的难度系数之和最小。
(nleq3 imes10^5) ， (1leq a_ile10^6) ， (1leq m leq 1.1 imes10^9)。
题解
静下心来想这道题吧！
设 (dp_i) 表示把前 (i) 个数分段后最小代价。
则朴素 dp ： (dp_i=min{dp_j+maxlimits_{k=j+1}^i a_k}) 。复杂度(O(n^2))。
考虑优化：
- 因为后一项和范围内 (max) 值有关，我们考虑使用一个单调队列，维护 ([j+1,i]) 区间内 (a_k) 的最大值。
维护一个最大值的单调队列，那么显然这个单调队列是单调不增的。 - 假设此队列中的值为((k_1,k_2,dots,k_m))（按序号顺序排序）。
考虑相邻的两个元素 (k_i) 和 (k_{i+1})。
(jin(k_{i},k_{i+1}]) 内的 (dp_j+maxlimits_{k=j+1}^i a_k) 中，后面那一项是相同的，为 (a_{k[i+1]}) 。 - 考虑使 (dp_j) 最小。
显然 (dp_i) 是单调不减的，那么一定当 (j) 取值 (k_i) 时， dp 值取最小。 - 对于队列内的多个元素，则需要对每对相邻元素都求其对应的 (dp+max a) ， 利用数据结构来快速找到这些值中最小的那一个，即为 (dp_i) 。
- 最后，考虑原 (dp) 式中 (j) 的取值范围。显然 (j) 满足 (sumlimits _{k=j+1}^i le m) ， 且 (j< i) 。
概述一下：
- 对于每个 (i) ，求出第一个满足条件的 (j) 。维护一个 ([j,i)) 的单调队列。
- 求出单调队列中每相邻一对的答案，用数据结构维护，其最小值计入 (dp_i) 中
复杂度(O(nlog n))
一些注意事项
- 关于数据结构：要求支持动态插入、删除、查询最值，可以使用 STL 内置的
multiset或手写平衡树。 - 关于队列：要支持查询此时队列中的每个元素， STL 内置的
deque无法满足要求。我们可以使用单纯数组模拟自行封装。 - 关于数据结构的查询：在队列长度 (ge 2) 时才有意义。（否则应该会RE罢）
代码
#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 3e5+5;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll ret=0;char ch=' ',c=getchar();
while(!(c>='0'&&c<='9'))ch=c,c=getchar();
while(c>='0'&&c<='9')ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
template <typename T> struct que{
T a[N]; int st=1,ed=0;
void dque(){st=1,ed=0;}
inline void clear(){st=1,ed=0;}
inline int size(){return ed-st+1;}
inline bool empty(){return !(ed-st+1);}
inline void pop_front(){st++;}
inline void pop_back(){ed--;}
inline T front(){return a[st];}
inline T back(){return a[ed];}
inline void push_back(T x){a[++ed] = x;}
inline T operator [] (int x){return a[st+x-1];}
};
int n;ll m;
ll dp[N],a[N],sm[N];
inline ll sum(int l,int r){return l>r ? -1ll*INF*INF : sm[r]-sm[l-1];}
multiset<ll> s;
que<int>q;
signed main(){
memset(dp,0x3f,sizeof(dp));
n = read() , m = read();
for(int i = 1 ; i <= n ; i ++)
a[i] = read() , sm[i] = sm[i-1] + a[i];
dp[0] = 0;
int j = 0; q.push_back(0);
for(int i = 1 ; i <= n ; i ++){
while(sum(j+1,i) > m) j++;
while(!q.empty() && q.front() < j) {
if(q.size() >= 2) s.erase(s.find(dp[q[1]]+a[q[2]]));
q.pop_front();
}
while(!q.empty() && a[q.back()] < a[i]){
if(q.size() >= 2) s.erase(s.find(dp[q[q.size()-1]] + a[q[q.size()]]));
q.pop_back();
}
if(!q.empty()) s.insert(dp[q.back()] + a[i]);
q.push_back(i);
dp[i] = dp[j] + a[q.front()];
if(q.size() >= 2) dp[i] = min(dp[i],*s.begin());
}
printf("%lld",dp[n]);
return 0;
}