本文共 2317 字，大约阅读时间需要 7 分钟。
题目描述：
当农夫约翰闲的没事干的时候，他喜欢坐下来看书。多年过去，他已经收集了 N 本书 (1 <= N <= 100,000)， 他想造一个新的书架来装所有书。每本书 i 都有宽度 W(i) 和高度 H(i)。书需要按顺序添加到一组书架上；比如说，第一层架子应该包含书籍1 ... k，第二层架子应该以第k + 1本书开始，以下如此。每层架子的总宽度最大为L（1≤L≤1,000,000,000）。每层的高度等于该层上最高的书的高度，并且整个书架的高度是所有层的高度的总和，因为它们都垂直堆叠。请帮助农夫约翰计算整个书架的最小可能高度。有N(1 <= N <= 100000)本书，每本书有一个宽度W(i)，高度H(i)，(1 <= H(i) <= 1,000,000; 1 <= W(i) <= L)。现在有足够多的书架，书架宽度最多是L (1 <= L <= 1,000,000,000)，把书按顺序（先放1，再放2.....）放入书架。某个书架的高度是该书架中所放的最高的书的高度。将所有书放入书架后，求所有书架的高度和的最小值？
/*很容易想到状态转移方程：f[i]=min(f[j]+max(h[j+1],h[j+2]……h[i])这样的时间复杂度是n^2点，显然过不了。那么可以想想，h[j]是随j的增大而单调不减的，是具有单调性的，所以可以线段树进行优化 */#include#include #include #include #include #include #define N 10000000#define INF 0x7f7f7f7f#define LL long long#define ls x<<1#define rs x<<1|1#define midd mid = (l+r)>>1#define lson l,mid,x<<1#define rson mid+1,r,x<<1|1using namespace std;int n;int hei,W[N];LL ans=(LL)0;int H[N],h[N],tag[N];LL f[N],val[N],L;void merge(int x){ H[x]=max(H[ls],H[rs]);h[x]=min(h[ls],h[rs]);val[x]=min(val[ls],val[rs]); return ;}void pushdown(int x){ if(!tag[x]) return ; tag[ls]=H[ls]=h[ls]=tag[rs]=H[rs]=h[rs]=tag[x]; val[ls]=f[ls]+(LL)tag[x];val[rs]=f[rs]+(LL)tag[x]; tag[x]=0;return ;}void change(int l,int r,int x,int ll,int rr,int c){ if(ll <= l && r <= rr) { if(c>=H[x]) { H[x]=h[x]=tag[x]=c;val[x]=f[x]+(LL)c;return ; } int mid=(l+r)>>1; pushdown(x); if(h[x<<1] <= c) change(lson,ll,rr,c); if(h[x<<1|1] <= c) change(rson,ll,rr,c); merge(x);return; } int mid=(l+r)>>1; pushdown(x); if(ll <= mid) change(lson,ll,rr,c); if(mid < rr) change(rson,ll,rr,c); merge(x);return ;}LL Get(int l,int r,int x,int ll,int rr){ if(ll <= l && r <= rr) return val[x]; int mid=(l+r)>>1;LL minn=1ll<<58; pushdown(x); if(ll <= mid) minn=min(minn,Get(lson,ll,rr)); if(rr > mid) minn=min(minn , Get(rson,ll,rr)); return minn;}void add(int l,int r,int x,int pos,LL c){ if(l == r){f[x]=c;return;} int mid=(l+r)>>1; pushdown(x); if(pos <= mid) add(lson,pos,c); else add(rson,pos,c); f[x]=min(f[ls],f[rs]); return ;}int main(){ scanf("%d%lld",&n,&L); LL last=(LL)1,sum=(LL)0; for(int i=1;i<=n;i++) { scanf("%d%d",&hei,&W[i]); sum+=(LL)W[i]; while(sum>L) sum-=(LL)W[last++]; change(1,n,1,1,i,hei); ans=Get(1,n,1,last,i); add(1,n,1,i+1,ans); } printf("%lld\n",ans); return 0;}/*5 105 79 28 513 23 821*/
转载地址：http://urqji.baihongyu.com/