题解 P1848 【[USACO12OPEN]书架Bookshelf】

· · 题解

有神仙钦定我写一篇题解，我写一篇好了。

自己都忘了怎么做了

先从一个 naive 的 O(n^2) dp 开始讲起。

$$f_i=\min(f_j+\max(h_{j+1},...,h_i))(w_{j+1}+...+w_i\leq L)$$ $w$ 这个限制我们可以通过**二分**得到。 现在我们把问题转化成： $$f_i=\min(f_j+\max(h_{j+1},...,h_i))(pos_i\leq j)$$ 其中 $pos_i$ 为第 $i$ 个位置的**最左端点**。 那么，这道题就成为一道非常套路的线段树优化 dp 了。 相信大家用线段树维护下面的操作都会吧： - 1. 区间赋值 - 2. 区间取 $\min

首先，我们先开一个单调栈，对于每个位置找出第一个大于 h_i 的位置 l，并将 [l+1,i] 这段区间内的 h 赋为 h_i。

我们发现每一个位置的 f 是确定的，我们每次只需区间修改 h 的值，然后维护 f+h 和 f 的最小值。

查询就直接在一段区间上查就行了。

顺便一提，这题因为 L 是给定的，所以可以用单调队列。如果每个位置的 L_i 是不固定的，这道题就只能用 \log 数据结构了。

Code\ Below: 
#include <bits/stdc++.h>
#define ll long long
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
const int maxn=100000+10;
const ll inf=1e18;
int n,L,w[maxn],h[maxn],pre[maxn],sta[maxn],top;ll sum[maxn],f[maxn],Min[maxn<<2],val[maxn<<2],tag[maxn<<2];
// Min 为 f + h 的最小值
// val 为 f 的最小值

inline int read()
{
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}

inline void pushup(int rt)
{
    Min[rt]=min(Min[lson],Min[rson]);
    val[rt]=min(val[lson],val[rson]);
}

inline void pushdown(int rt)
{
    if(tag[rt]!=inf)
    {
        Min[lson]=val[lson]+tag[rt];
        Min[rson]=val[rson]+tag[rt];
        tag[lson]=tag[rson]=tag[rt];tag[rt]=inf;
    }
}

void build(int l,int r,int rt)
{
    Min[rt]=val[rt]=tag[rt]=inf;
    if(l == r) return ;
    int mid=(l+r)>>1;
    build(l,mid,lson);build(mid+1,r,rson);
}

void update(int L,int R,int C,int l,int r,int rt)
{
    if(L <= l && r <= R)
    {
        Min[rt]=val[rt]+C;tag[rt]=C;
        return ;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(L <= mid) update(L,R,C,l,mid,lson);
    if(R > mid) update(L,R,C,mid+1,r,rson);
    pushup(rt);
}

void modify(int x,int l,int r,int rt)
{
    if(l == r)
    {
        Min[rt]=inf;val[rt]=f[l-1];
        return ;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(x <= mid) modify(x,l,mid,lson);
    else modify(x,mid+1,r,rson);
    pushup(rt);
}

ll query(int L,int R,int l,int r,int rt)
{
    if(L <= l && r <= R) return Min[rt];
    pushdown(rt);
    int mid=(l+r)>>1;ll ans=inf;
    if(L <= mid) ans=min(ans,query(L,R,l,mid,lson));
    if(R > mid) ans=min(ans,query(L,R,mid+1,r,rson));
    return ans;
}

int main()
{
    n=read(),L=read();
    for(int i=1;i<=n;i++)
    {
        h[i]=read(),w[i]=read();
        sum[i]=sum[i-1]+w[i];
    }
    sta[++top]=1;
    for(int i=2;i<=n;i++)
    {
        while(top&&h[i]>h[sta[top]]) top--;
        if(top) pre[i]=sta[top];
        sta[++top]=i;
    }
    build(1,n,1);
    for(int i=1;i<=n;i++)
    {
        modify(i,1,n,1);//初始化决策点
        if(pre[i]+1<=i) update(pre[i]+1,i,h[i],1,n,1);// 区间赋值
        int l=lower_bound(sum,sum+i+1,sum[i]-L)-sum;//二分左端点
        if(l<i) f[i]=query(l+1,i,1,n,1);//区间查询
    }
    printf("%lld\n",f[n]);
    return 0;
}