[USACO12OPEN]Bookshelf G

题目链接：[USACO12OPEN]Bookshelf G

---

有一个很显然的式子：
dp[i] = min{ dp[j] + max{ a[j+1]->a[i] } }
然后尺取可以找到最远的可行的j。
直接递推复杂度太高。
我们可以发现可以用单调队列维护可行区间，然后用一个multiset维护单调队列里面的最大值即可。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,a[N],b[N],L=1,R,sum,dp[N],q[N];
multiset<int> s;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	scanf("%lld %lld",&b[i],&a[i]);
	for(int i=1,j=0;i<=n;i++){
		if(a[i]>m)	return puts("-1"),0;
		sum+=a[i];
		while(sum>m)	sum-=a[++j];
		while(L<=R&&q[L]<j)	s.erase(s.find(dp[q[L]]+b[q[L+1]])),L++;
		while(L<=R&&b[q[R]]<=b[i]){
			if(L<R)	s.erase(s.find(dp[q[R-1]]+b[q[R]]));
			R--;	
		}
		q[++R]=i;	if(L<R)	s.insert(dp[q[R-1]]+b[q[R]]);
		dp[i]=dp[j]+b[q[L]];
		if(L<R)	dp[i]=min(dp[i],*s.begin());
	}
	cout<<dp[n];
	return 0;
}