【POJ】3017 Cut the Sequence

 1 #include<cstdio>
 2 #define MAXN 100010
 3 #define MIN(a,b) ((a)<(b)?(a):(b))
 4 typedef __int64 LL;
 5 LL limit,a[MAXN],dp[MAXN];
 6 int n,Q[MAXN];
 7 LL DoIt()
 8 {
 9     LL sum;
10     int i,j,k,front,rear;
11     for(i=1;i<=n;i++)
12     {
13         if(a[i]>limit)
14             return -1;
15     }
16     sum=dp[0]=0;
17     front=0;
18     rear=-1;
19     for(i=k=1;i<=n;i++)
20     {
21         sum+=a[i];
22         for(;sum>limit;k++)
23             sum-=a[k];
24         for(;front<=rear&&Q[front]<k;front++);
25         for(;front<=rear&&a[Q[rear]]<=a[i];rear--);
26         Q[++rear]=i;
27         dp[i]=dp[k-1]+a[Q[front]];
28         for(j=front;j<rear;j++)
29             dp[i]=MIN(dp[i],dp[Q[j]]+a[Q[j+1]]);
30     }
31     return dp[n];
32 }
33 int main()
34 {
35     int i;
36     while(~scanf("%d%I64d",&n,&limit))
37     {
38         for(i=1;i<=n;i++)
39             scanf("%I64d",&a[i]);
40         printf("%I64d\n",DoIt());
41     }
42     return 0;
43 }