http://poj.org/problem?id=3017

单调队列优化DP

萌新不知道哪里写炸了，超时了。

#include <cstdio>
#include <iostream>
#include <set>

#define int long long

using namespace std;

int n,m;
int a[100005];
int num[100005];
int dp[100005];
int q[100005],l=1,r=0;
int ans=-99999999;

multiset<int> s;

signed main()
{
    int i,j,k;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]>m)
        {
            cout<< -1;
            return 0;
        }
        num[i]=num[i-1]+a[i];
    }
    int lb=1;//极端

    for(i=1;i<=n;i++)
    {
        while(num[i]-num[lb-1]>m)lb++;//更新极端
        while(l<=r&&num[i]-num[q[l]-1]>m)//更新队列左边
        {
            if(l<r)s.erase(dp[q[l]]+a[q[l+1]]);
            l++;
        }
        while(l<=r&&a[q[r]]<=a[i])//更新队列右边
        {
            if(l<r)s.erase(dp[q[r-1]]+a[q[r]]);
            r--;
        }
        //入队
        q[++r]=i;
        if(l<r)s.insert(dp[q[r-1]]+a[i]);
        //转移
        dp[i]=dp[lb-1]+a[q[l]];
        if(l<r)dp[i]=min(dp[i],*s.begin());
    }
    cout<<dp[n];
    return 0;
}