网站名称和备案的不一样/免费学生网页制作成品

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
varleft,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);
vark:longint;
begink:=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);
vark:longint;
begink:=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);
beginif s[left[left[t]]]>s[right[t]] then beginrightrotate(t);maintain(right[t]);maintain(t);end;if s[right[left[t]]]>s[right[t]] then beginleftrotate(left[t]);rightrotate(t);maintain(left[t]);maintain(right[t]);maintain(t);end;if s[right[right[t]]]>s[left[t]] then beginleftrotate(t);maintain(left[t]);maintain(t);end;if s[left[right[t]]]>s[left[t]] then beginrightrotate(right[t]);leftrotate(t);maintain(left[t]);maintain(right[t]);maintain(t);end;
end;procedure insert(var t:longint;v:int64);
beginif t=0 then begininc(tot);t:=tot;key[t]:=v;s[t]:=1;left[t]:=0;right[t]:=0;endelse begininc(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;
begindec(s[t]);if (key[t]=v) or( (v<key[t]) and (left[t]=0) )or ((v>=key[t]) and (right[t]=0)) then begindelete:=key[t];if (left[t]=0) or (right[t]=0) thent:=left[t]+right[t]else key[t]:=delete(left[t],key[t]+1);endelseif v<key[t] thendelete:=delete(left[t],v)else delete:=delete(right[t],v);
end;function searchmin(var t:longint):int64;
beginif left[t]=0 then exit(key[t]);exit(searchmin(left[t]));
end;function into:boolean;
beginreadln(n,m);sum[0]:=0;for i:=1 to n do beginread(a[i]);sum[i]:=sum[i-1]+a[i];if a[i]>m then exit(false);end;exit(true);
end;beginif into then begint:=0;tot:=0;head:=1;tail:=1;deci:=0;for i:=1 to n do beginwhile sum[i]-sum[deci]>m do inc(deci);while (head<tail) and (q[head]<=deci) do begindelete(t,f[d[head]]+a[q[head]]);inc(head);end;while (head<tail) and (a[i]>=a[q[tail-1]]) do begindelete(t,f[d[tail-1]]+a[q[tail-1]]);dec(tail);end;q[tail]:=i;if head<tail thend[tail]:=q[tail-1]else d[tail]:=deci;insert(t,f[d[tail]]+a[i]);inc(tail);if d[head]<deci then begindelete(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]);endelse writeln('-1');readln;readln;
end.