Description：

将一个序列分成很多段，每一段和不超过 $m$ ，最小化每段最大值的和。

$1\leqslant n \leqslant10^5$

Solution：

$$ \begin{align}f[i]=\min_{j=0,s[i]-s[j]\leqslant m}^{i-1}(f[j]+\max_{k=j+1}^i h[k])\end{align} $$

转移是 $O(n^2)$ 的，考虑优化，看数据范围不是 $O(n)$ 就是 $O(n\log n)$ ，最大值最小值都可以用线段树，本题思路已经不难想到了，按照数据结构优化 $DP$ 的套路，开三棵线段树，一棵维护 $\max h[k]$ 即 $h$ 的后缀最大值，一棵维护 $f[j]$ ，一棵维护 $\max h[k]+f[j]$ ，转移就是在第三棵线段树上求最值， $f[j]$ 很好维护，因为只有单点修改操作， $\max h[k]$ 也很好维护，但是却没有这么简单，因为虽然 $\max h[k]$ 上单点修改了一次，在第三棵线段树上却可能有很多区间的值要发生变化，而且变化没有什么规律，这就不能简单操作，考虑如何把取最大值这个操作用一种更容易维护的方式表示出来，先用单调栈求出每个点左边比它大的第一个位置，这个位置左边不会受影响，当前位置右边也不会受影响，这样就把 $\max$ 操作变成了第一棵线段树上的区间赋值操作，然后这样第三棵线段树上改动的区间和第一棵线段树是一样的，就可以直接操作了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

typedef long long ll; 

int h[MAXN];

stack<int> s;

int lef[MAXN];

struct node

{

	int lc,rc;

	ll res,dp,tagv;

	node(){tagv = -1;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void pushdown(int rt)

{

	if(t[rt].tagv == -1)return;

	t[t[rt].lc].res = t[t[rt].lc].dp + t[rt].tagv;

	t[t[rt].lc].tagv = t[rt].tagv;

	t[t[rt].rc].res = t[t[rt].rc].dp + t[rt].tagv;

	t[t[rt].rc].tagv = t[rt].tagv;

	t[rt].tagv = -1;

	return;

}

void addv(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].tagv = k;

		t[rt].res = t[rt].dp + t[rt].tagv;

		return;

	}

	pushdown(rt);

	if(L <= mid)addv(t[rt].lc,L,R,k,l,mid);

	if(R > mid)addv(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].res = min(t[t[rt].lc].res,t[t[rt].rc].res);

	return;

}

void addf(int rt,int p,int k,int l,int r)

{

	if(l == r)

	{

		t[rt].dp += k;

		t[rt].res = t[rt].dp + t[rt].tagv;

		return;

	}

	pushdown(rt);

	if(p <= mid)addf(t[rt].lc,p,k,l,mid);

	else addf(t[rt].rc,p,k,mid + 1,r);

	t[rt].dp = min(t[t[rt].lc].dp,t[t[rt].rc].dp);

	t[rt].res = min(t[t[rt].lc].res,t[t[rt].rc].res);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].res;

	int res = 0x3f3f3f3f;

	pushdown(rt);

	if(L <= mid)res = min(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = min(res,query(t[rt].rc,L,R,mid + 1,r));

	return res;

}

int f[MAXN];

ll sum[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&h[i]);

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + h[i];

	h[0] = 0x3f3f3f3f;s.push(0);

	for(int i = 1;i <= n;++i)

	{

		while(!s.empty() && h[s.top()] < h[i])s.pop();

		lef[i] = s.top();s.push(i);

	}//cout << endl;

	f[0] = 0;

	build(root,0,n);

	for(int i = 1,cur = 0;i <= n;++i)

	{

		addv(root,lef[i],i,h[i],0,n);

		while(sum[i] - sum[max(0,cur - 1)] > m)++cur;

		f[i] = query(root,max(0,cur - 1),i - 1,0,n);

		addf(root,i,f[i],0,n);

	}

	cout << f[n] << endl;

	return 0;

}