[USACO12OPEN]书架Bookshelf

算法：DP+单调队列维护

题面描述

有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…）放入书架。某个书架的高度是该书架中所放的最高的书的高度。将所有书放入书架后，求所有书架的高度和的最小值。

输入
第1行：两个数N和L；
接下来N行：每行两个数H_i和W_i.
输出
一个数，书架高度的最小值。

样例输入
5 10
5 7
9 2
8 5
13 2
3 8
样例输出
21

解题思路

设f[i]表示以第 i 本书结尾时所有书架高度和的最小值（某书架的高度是该书架中所放的最高书的高度）。
容易得到转移方程：f[i]=min(f[j]+max(h[j+1],h[j+2]……h[i])) （j<i）
此时时间复杂度是O(n²)，肯定会TLE。
于是我们由某个书架的高度是该书架中所放的最高的书的高度可知，h[j]是随j的增大而单调不减的，因此我们可以采用单调队列优化。

单调队列优化不会的请自行百度搜索！！！

代码演示

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define MAXN 100005
using namespace std;
long long n,m,cnt,i,j,flag,l,r,w[MAXN],h[MAXN],f[MAXN],q[MAXN];
int read()
{
    int x=0,f=1;
    char ch=getchar();
    if (ch=='-') f=-1;
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main()
{
    n=read();
    m=read(); 
    for(i=1;i<=n;i++)
    {
        h[i]=read();
        w[i]=read();
    }
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0]=0;
    flag=1;
    q[++r]=0;
    l++;
    for(i=1;i<=n;i++)
    {
        cnt+=w[i];
        while(cnt>m)
        {
            flag++;
            cnt-=w[flag-1];
        }
        while (l<=r&&q[l]<flag) l++;
        while (l<=r&&h[q[r]]<=h[i]) r--;
        q[++r]=i;
        for (j=l;j<r;j++) f[i]=min(f[i],f[q[j]]+h[q[j+1]]);
        f[i]=min(f[i],f[flag-1]+h[q[l]]);//特别注意这里还有一种情况！
    }
    printf("%lld",f[n]);
    return 0;
}