dp+单调性+平衡树
在看某篇论文中看到这道题，但是那篇论文不如这个http://www.cnblogs.com/staginner/archive/2012/04/02/2429850.html 大神的空间写的好（还是说我太弱需要详解……）。
其实要说的在大神的博客里面已经说的很好……
比如f[i]，然后j表示满足a[j+1]+a[j+2]+……+a[i]<=m的最小值。然后我们假定a[j]--a[i]中最大数的下标为k，那么就有j+1<=l<=k时，f[j+1]+a[k]<=f[j+2]+a[k]<=f[j+3]+a[k]……<=f[k-1]+a[k]，也就是只要在把在k前或者k到i的区间分为一个区间，那么这个区间的最大值就是a[k]。这样f数组就是递增的。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 var left,right,s,q,d:array[0..501000]of longint; key,a,sum,f:array[0..500100]of int64; i,j,k,l,n,tot,t,head,tail,deci:longint; m:int64; procedure rightrotate(var t:longint); var k:longint; begin k:=left[t]; left[t]:=right[k]; right[k]:=t; s[k]:=s[t]; s[t]:=s[left[t]]+s[right[t]]+1; t:=k; end; procedure leftrotate(Var t:longint); var k:longint; begin k:=right[t]; right[t]:=left[k]; left[k]:=t; s[k]:=s[t]; s[t]:=s[left[t]]+s[right[t]]+1; t:=k; end; procedure maintain(var t:longint); begin if s[left[left[t]]]>s[right[t]] then begin rightrotate(t); maintain(right[t]); maintain(t); end; if s[right[left[t]]]>s[right[t]] then begin leftrotate(left[t]); rightrotate(t); maintain(left[t]); maintain(right[t]); maintain(t); end; if s[right[right[t]]]>s[left[t]] then begin leftrotate(t); maintain(left[t]); maintain(t); end; if s[left[right[t]]]>s[left[t]] then begin rightrotate(right[t]); leftrotate(t); maintain(left[t]); maintain(right[t]); maintain(t); end; end; procedure insert(var t:longint;v:int64); begin if t=0 then begin inc(tot); t:=tot; key[t]:=v; s[t]:=1; left[t]:=0; right[t]:=0; end else begin inc(s[t]); if v<key[t] then insert(left[t],v) else insert(right[t],v); maintain(t); end; end; function delete(var t:longint;v:int64):int64; begin dec(s[t]); if (key[t]=v) or( (v<key[t]) and (left[t]=0) )or ((v>=key[t]) and (right[t]=0)) then begin delete:=key[t]; if (left[t]=0) or (right[t]=0) then t:=left[t]+right[t] else key[t]:=delete(left[t],key[t]+1); end else if v<key[t] then delete:=delete(left[t],v) else delete:=delete(right[t],v); end; function searchmin(var t:longint):int64; begin if left[t]=0 then exit(key[t]); exit(searchmin(left[t])); end; function into:boolean; begin readln(n,m); sum[0]:=0; for i:=1 to n do begin read(a[i]); sum[i]:=sum[i-1]+a[i]; if a[i]>m then exit(false); end; exit(true); end; begin if into then begin t:=0; tot:=0; head:=1; tail:=1; deci:=0; for i:=1 to n do begin while sum[i]-sum[deci]>m do inc(deci); while (head<tail) and (q[head]<=deci) do begin delete(t,f[d[head]]+a[q[head]]); inc(head); end; while (head<tail) and (a[i]>=a[q[tail-1]]) do begin delete(t,f[d[tail-1]]+a[q[tail-1]]); dec(tail); end; q[tail]:=i; if head<tail then d[tail]:=q[tail-1] else d[tail]:=deci; insert(t,f[d[tail]]+a[i]); inc(tail); if d[head]<deci then begin delete(t,f[d[head]]+a[q[head]]); d[head]:=deci; insert(t,f[deci]+a[q[head]]); end; f[i]:=searchmin(t); end; writeln(f[n]); end else writeln('-1'); readln; readln; end.