【原題見(jiàn)
這里】
本沙茶見(jiàn)過(guò)的最猥瑣的DP題啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊……
設(shè)F[i]為將A[1..i]拆分成若干段的最大值最小和，則有
F[i]=min{F[j] + max[j+1, i]}（B[i]<=j<i），其中max[j+1, i]表示A[j+1..i]中的最大值，B[i]表示從i向左最遠(yuǎn)可以延伸到哪里（也就是滿足SUM[x..i]<=m的最小的x值）。B數(shù)組可以通過(guò)預(yù)處理在O(N)時(shí)間內(nèi)得到。
邊界：F[0]=0。
下面是優(yōu)化過(guò)程。JZP神犇的論文里面已經(jīng)夠詳細(xì)了。這里只是簡(jiǎn)要說(shuō)明一下。
首先容易證明，F(xiàn)是單調(diào)遞增的。
然后一個(gè)很關(guān)鍵的定理是：
若F[i]的最優(yōu)決策為j，則有A[j]>∀A[k]（j<k<=i）。證明：用反證法。若A[j+1..i]中存在不小于A[j]的值，則可得max[j..i]=max[j+1..i]，又因?yàn)镕單調(diào)遞增，所以F[j-1]+max[j..i]<=F[j]+max[j+1.i]，即決策(j-1)一定不比決策j差，也就是決策j不可能成為最優(yōu)決策。
這樣，可以維護(hù)一個(gè)下標(biāo)嚴(yán)格遞增、A值嚴(yán)格遞減的隊(duì)列Q（即對(duì)于隊(duì)列中的任意兩個(gè)元素Q[i]和Q[j]，若i<j，則Q[i].pos<Q[j].pos且A[Q[i].pos]>A[Q[j].pos]，具體實(shí)現(xiàn)時(shí)pos可省略）。則可能成為最優(yōu)決策的決策要么是在這個(gè)隊(duì)列Q里，要么是B[i]。對(duì)于隊(duì)列中的某個(gè)決策Q[x]，該決策導(dǎo)出的值為F[Q[x]]+A[Q[x + 1]]（很容易證明max[Q[x]+1..i]=A[Q[x + 1]]），找到這些導(dǎo)出的值中的最小值即可（注意，隊(duì)尾元素沒(méi)有導(dǎo)出值）。對(duì)于決策B[i]，只需要在預(yù)處理的時(shí)候同時(shí)得到MAX[i]=max[B[i]+1..i]即可（也可以在O(N)時(shí)間內(nèi)得到），決策B[i]導(dǎo)出的值為F[B[i]]+MAX[i]。
在刪除隊(duì)首過(guò)時(shí)元素的時(shí)候，需要把導(dǎo)出值也刪除，刪除隊(duì)尾元素也一樣，插入的時(shí)候，若插入前隊(duì)列不為空，則需要插入一個(gè)導(dǎo)出值。也就是，需要一個(gè)支持在對(duì)數(shù)時(shí)間內(nèi)進(jìn)行插入、刪除任意結(jié)點(diǎn)、找最小值等操作，顯然用平衡樹(shù)最好。
注意事項(xiàng)：
（1）不管是在隊(duì)首刪除還是在隊(duì)尾刪除，若刪除的是隊(duì)列中的最后一個(gè)元素，則不需要在平衡樹(shù)中刪除導(dǎo)出值；
（2）插入時(shí)，若插入前隊(duì)列為空，則不需要在平衡樹(shù)中插入導(dǎo)出值；
（3）在計(jì)算F[i]時(shí)，應(yīng)先將決策i壓入。
代碼：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re1(i, n) for (int i=1; i<=n; i++)
const int MAXN = 100001;
struct node {
int l, r, p, sz0, sz, mul;
long long v;
} T[MAXN];
const long long INF = ~0Ull >> 2;
int n, N = 0, a[MAXN], b[MAXN], MAX[MAXN], Q[MAXN], front = 0, rear = -1, root = 0;
long long m, F[MAXN], res = 0;
void init()
{
cin >> n >> m;
re1(i, n) scanf("%d", &a[i]); a[0] = ~0U >> 2;
}
void prepare()
{
re1(i, n) if (a[i] > m) {res = -1; return;}
int x = 1;
long long sum = 0;
re1(i, n) {
for (sum+=a[i]; sum>m; sum-=a[x++]) ;
b[i] = x - 1;
}
re1(i, n) {
for (; front<=rear && Q[front]<=b[i]; front++) ;
for (; front<=rear && a[Q[rear]]<=a[i]; rear--) ;
Q[++rear] = i; MAX[i] = a[Q[front]];
}
}
void vst(int x)
{
if (x) {
cout << T[x].v << ' ';
vst(T[x].l); vst(T[x].r);
}
}
void slc(int _p, int _c)
{
T[_p].l = _c; T[_c].p = _p;
}
void src(int _p, int _c)
{
T[_p].r = _c; T[_c].p = _p;
}
void upd(int x)
{
T[x].sz0 = T[T[x].l].sz0 + T[T[x].r].sz0 + T[x].mul;
T[x].sz = T[T[x].l].sz + T[T[x].r].sz + 1;
}
void lrot(int x)
{
int y = T[x].p;
if (y == root) T[root = x].p = 0; else {int p = T[y].p; if (y == T[p].l) slc(p, x); else src(p, x);}
src(y, T[x].l); slc(x, y); T[x].sz0 = T[y].sz0; T[x].sz = T[y].sz; upd(y);
}
void rrot(int x)
{
int y = T[x].p;
if (y == root) T[root = x].p = 0; else {int p = T[y].p; if (y == T[p].l) slc(p, x); else src(p, x);}
slc(y, T[x].r); src(x, y); T[x].sz0 = T[y].sz0; T[x].sz = T[y].sz; upd(y);
}
void maintain(int x, bool ff)
{
int z;
if (ff) {
if (T[T[T[x].r].r].sz > T[T[x].l].sz) {z = T[x].r; lrot(z);}
else if (T[T[T[x].r].l].sz > T[T[x].l].sz) {z = T[T[x].r].l; rrot(z); lrot(z);} else return;
} else {
if (T[T[T[x].l].l].sz > T[T[x].r].sz) {z = T[x].l; rrot(z);}
else if (T[T[T[x].l].r].sz > T[T[x].r].sz) {z = T[T[x].l].r; lrot(z); rrot(z);} else return;
}
maintain(T[z].l, 0); maintain(T[z].r, 1); maintain(z, 0); maintain(z, 1);
}
int find(long long _v)
{
int i = root;
long long v0;
while (i) {
v0 = T[i].v;
if (_v == v0) return i; else if (_v < v0) i = T[i].l; else i = T[i].r;
}
return 0;
}
int Find_Kth(int K)
{
int i = root, s0, m0;
while (1) {
s0 = T[T[i].l].sz0; m0 = T[i].mul;
if (K <= s0) i = T[i].l; else if (K <= s0 + m0) return i; else {K -= s0 + m0; i = T[i].r;}
}
}
void ins(long long _v)
{
if (!root) {
T[++N].v = _v; T[N].l = T[N].r = T[N].p = 0; T[N].sz0 = T[N].sz = T[N].mul = 1; root = N;
} else {
int i = root, j;
long long v0;
while (1) {
T[i].sz0++; v0 = T[i].v;
if (_v == v0) {T[i].mul++; return;} else if (_v < v0) j = T[i].l; else j = T[i].r;
if (j) i = j; else break;
}
T[++N].v = _v; T[N].l = T[N].r = 0; T[N].sz0 = T[N].sz = T[N].mul = 1; if (_v < v0) slc(i, N); else src(i, N);
while (i) {T[i].sz++; maintain(i, _v > T[i].v); i = T[i].p;}
}
}
void del(int x)
{
if (T[x].mul > 1) {
T[x].mul--; while (x) {T[x].sz0--; x = T[x].p;}
} else {
int l = T[x].l, r = T[x].r, p;
if (l && r) {
int y; while (y = T[l].r) l = y;
T[x].v = T[l].v; T[x].mul = T[l].mul; p = T[l].p;
if (l == T[p].l) slc(p, T[l].l); else src(p, T[l].l);
while (p) {upd(p); p = T[p].p;}
} else {
if (x == root) T[root = l + r].p = 0; else {p = T[x].p; if (x == T[p].l) slc(p, l + r); else src(p, l + r); while(p) {upd(p); p = T[p].p;}}
}
}
}
long long h(int x)
{
return F[Q[x]] + a[Q[x + 1]];
}
void solve()
{
F[0] = 0; front = 0; rear = 0; Q[0] = 0;
re1(i, n) {
for (; front<=rear && Q[front]<b[i];) {if (front < rear) del(find(h(front))); front++;}
for (; front<=rear && a[Q[rear]]<=a[i];) {if (front < rear) del(find(h(rear - 1))); rear--;}
Q[++rear] = i; if (front < rear) ins(h(rear - 1));
if (root) F[i] = T[Find_Kth(1)].v; else F[i] = INF;
if (F[b[i]] + MAX[i] < F[i]) F[i] = F[b[i]] + MAX[i];
}
res = F[n];
}
void pri()
{
cout << res << endl;
}
int main()
{
init();
prepare();
if (!res) solve();
pri();
return 0;
}