P1848 [USACO12OPEN] Bookshelf G

• 开int 95分
• 开long long 0分

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int h[200010],hh[200010]
int x[200010],dp[200010];
int l,r,s,qq;
main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>h[i]>>hh[i];
		dp[i]=INT_MAX;
	}
	dp[0]=0;
    l=r=1;
	for(int i=1;i<=n;i++)
	{
		s+=hh[i];
		while(s>m)
		{
			s-=hh[qq];
			++qq;
		}
		while(l<=r&&x[l]<qq)
			++l;
		while(l<=r&&h[x[r]]<=h[i])
			--r;
		x[++r]=i;
		for(int j=l;j<=r-1;j++)
			dp[i]=min(dp[i],dp[x[j]]+h[x[j+1]]);
		dp[i]=min(dp[i],dp[qq-1]+h[x[l]]);
	}
	cout<<dp[n];
}