poj 3017

제목: n개의 수를 주고 구분된 구간의 모든 최대치의 합을 구합니다. (구분 조건은 이 구간의 합이 m보다 작음)
먼저 dp를 생각하기 쉽다. 공식 dp[i]=min(dp[i], dp[j]+max(a[j+1]+....a[i]))
이것은 O(n^2)의 복잡도이다
그러면 단조로운 체감 서열을 유지하면 매번 구하는 것은 단조로운 대기열 안에서 조건을 만족시키는 요소들이다. 그리고 dp 체감 공식에 따라 해답을 구한다.
Hint: 여러 조로 제출하면

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define ll long long
#define N 111111
const ll inf = 1111111111111;

ll sum;
ll a[N];
int n;
ll m;
int que[N];
ll dp[N];

ll slove(){
    sum = 0;
    int k  = 0;
    int l = 0;
    int r = -1;
    dp[0] = 0;
    for(int i=1;i<=n;i++){
        scanf("%I64d",&a[i]);
        if(a[i]>m) return -1;
        sum+=a[i];
        while(sum>m) sum-=a[++k]; //        m     
        while(l<=r&&a[que[r]]<=a[i]) --r;//      ，    a【i】           ，         
        que[++r] = i;
        while(l<=r&&que[l]<=k) l++;
        dp[i] = inf;
        int h = k;
       // printf(" h ---%d
 l--%d--r---%d
%d
",h,l,r,que[r]);
        for(int j=l;j<=r;j++){
            ll tmp = dp[h] + a[que[j]];
            if(tmp < dp[i]) dp[i] = tmp;
            h = que[j];
        }
    }
    return dp[n];
}

int main(){
    scanf("%d%I64d",&n,&m);
    printf("%I64d
",slove());
}