裁剪序列

给定一个长度为 N 的序列 A ，要求把该序列分成若干段，在满足“每段中所有数的和”不超过M的前提下，让“每段中所有数的最大值”之和最小。

试计算这个最小值。

输入格式
第一行包含两个整数N和M。

第二行包含N个整数，表示完整的序列A。

输出格式
输出一个整数，表示结果。

如果结果不存在，则输出-1。

样例

8 17
2 2 2 8 1 8 2 1

输出

12

单调队列+优先级队列优化

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N=100050;
long long dp[N],vise[N];//用于懒惰标记
int  deq[N],p[N],A[N];
long long n,m;
//使用小根堆的技巧，插入相反数
priority_queue<pair<long long,int>> que;

int main(){
    scanf("%lld %lld",&n,&m);
    long long arr[n+1];
    for(int i=1;i<=n;i++){
        scanf("%lld",&arr[i]);
        if(arr[i]>m){
            cout<<-1<<endl;
            return 0;
        }

    }
    long long sum=0;
    int head=0;
    int tail=-1;
    int pre=1;
    //单调队列获得一段区间中的最值，不需要使用线段树，ST时间复杂度线性。
    for(int i=1;i<=n;i++){
        sum=sum+arr[i];
        for(;sum>m;pre++)sum=sum-arr[pre];
        p[i]=pre-1;
        for(;tail>=head&&deq[head]<pre;head++);
        for(;tail>=head&&arr[deq[tail]]<=arr[i];tail--);
        deq[++tail]=i;
        //先插入再更新 
        A[i]=arr[deq[head]];
    }
    head=0;
    tail=-1;
    sum=0;
    pre=1;
    for(int i=1;i<=n;i++){
        //贪心更新，尽可能使得当前这一段区间的长度够大
        dp[i]=dp[p[i]]+A[i];
        //维持arr[i]的下标递增，值递减的单调队列，注意区间右端点我们可以用之前求解的p快速获得
        for(;tail>=head&&deq[head]<p[i]+1;head++)vise[deq[head]]=0;
        for(;tail>=head&&arr[deq[tail]]<=arr[i];tail--)vise[deq[tail]]=0;
        deq[++tail]=i;//先将该元素插入队列
        //更新优先级队列，只有单调队列中元素超过两个时才可以更新
        if(tail>head){
            que.push({-dp[deq[tail-1]]-arr[deq[tail]],deq[tail-1]});
            vise[deq[tail-1]]=-dp[deq[tail-1]]-arr[deq[tail]];
        }
        //根据惰性删除，删除优先级队列中已经失效的值。
        for(;!que.empty()&&(vise[que.top().second]!=que.top().first||vise[que.top().second]==0);que.pop());
        if(!que.empty())dp[i]=min(dp[i],-que.top().first);
    }
    cout<<dp[n]<<endl;
    return 0;
}