题解 P1848 【[USACO12OPEN]书架Bookshelf】

chdy · 2019-05-13 06:58:22 · 题解

这道题题意还是很明确的我是看着splay刷的没想到是dp。

首先题目中很详细的说书要一本一本放，这便为我们的动态规划划分好了阶段了，显然一个状态是 f[i]表示前i本书放到了若干个书架上的高度最小总和。

f[i]=min{f[j]+cost[j+1][i]} 

其中j∈flag-1~i-1 cost[j+1][i]=MAX{b[j+1]~b[i]};

• 发现这个东西需要枚举决策j 复杂度是n^2的考虑优化，但是显然我们感觉不太好优化，我们仔细看这个方程可以发现 对于 k<=j f[k]<=f[j] 这说明了 是具有单调性的。

• 然后对于每一个b来说都有一个控制区间在此区间内最左端的端点是最优的，单调队列存储一下这个b单调递减的区间然后 每次状态转移用当前区间的左端点+下个区间的b来更新即可。

• 少了一点是对于第一个决策点我们其实还有一个隐藏的决策点 就是flag-1+第一个决策点。注意好这些就是可以在不开o2的情况下得到95分。

// luogu-judger-enable-o2
#include<iostream>
#include<queue>
#include<iomanip>
#include<cctype>
#include<cstdio>
#include<deque>
#include<utility>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define INF 1000000000
#define ll long long
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define v(x) t[x].v
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void put(ll x)
{
    x<0?putchar('-'),x=-x:0;
    ll num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar('\n');return;
}
const ll MAXN=100010;
ll n,m,maxx,cnt,flag;
ll a[MAXN],b[MAXN];
ll f[MAXN];//f[i]表示前i本书放入若干个书架的最小花费。
ll q[MAXN],l,r;
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();
    for(ll i=1;i<=n;++i)b[i]=read(),a[i]=read();
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0]=0;flag=1;q[++r]=0;++l;
    for(ll i=1;i<=n;++i)
    {
        cnt+=a[i];
        while(cnt>m)++flag,cnt-=a[flag-1];
        while(l<=r&&q[l]<flag)++l;
        while(l<=r&&b[q[r]]<=b[i])--r;
        q[++r]=i;
        for(ll j=l;j<r;++j)f[i]=min(f[i],f[q[j]]+b[q[j+1]]);
        f[i]=min(f[i],f[flag-1]+b[q[l]]);
    }
    put(f[n]);
    return 0;
}

当然尽量要不开o2尽管这种优化看起来非常短非常好但是不够优秀。

考虑线段树优化 线段树上存在每一个点包含当前f值对于每一个b我们将其暴力区间覆盖。

然后查询区间最小值也就是最优决策即可。注意暴力覆盖的时候考虑时间复杂度有点高，采取两个优化线段树中存一个s h 一个高度取最大一个高度取最小，如果最小高度>=b直接跳过，如果当前最大高度<=b则懒标记直接区间覆盖即可。

• 复杂度的证明：对于一个值各不相同的区间第一次肯定是暴力覆盖 然后变成了一个单调递减的 这样的话下一次修改一部分是直接区间覆盖了，一部分是跳过了跳过了。然后均摊复杂度仍为nlogn.很完美的解决了这种类型的dp优化。

• 当然还有set优化不过很不好写（我上次写set优化真的难受死了那就分享两种优化方法好了~

• segmenttree：

#include<iostream>
#include<queue>
#include<iomanip>
#include<cctype>
#include<cstdio>
#include<deque>
#include<utility>
#include<cmath>
#include<ctime>
#include<cstring>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define INF 10000000000000ll
#define ll long long
#define l(x) t[x].l
#define r(x) t[x].r
#define sum(x) t[x].sum
#define s(x) t[x].s
#define h(x) t[x].h
#define tag(x) t[x].tag
#define g(x) t[x].g
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
inline void put(ll x)
{
    x<0?putchar('-'),x=-x:0;
    int num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar('\n');return;
}
const int MAXN=100010;
int n,m,flag;
int a[MAXN],b[MAXN];
ll f[MAXN],maxx,cnt;//f[i]表示前i本书放入若干个书架的最小花费。
inline ll min1(ll x,ll y){return x>y?y:x;}
inline ll max1(ll x,ll y){return x>y?x:y;}
struct wy
{
    int l,r;
    ll sum,g;
    ll h,s;
    int tag;
}t[MAXN<<2];
inline void build(int p,int l,int r)
{
    l(p)=l;r(p)=r;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    return;
}
inline void pushdown(int p)
{
    tag(p<<1)=tag(p<<1|1)=tag(p);
    s(p<<1)=s(p<<1|1)=h(p<<1)=h(p<<1|1)=tag(p);
    sum(p<<1)=g(p<<1)+tag(p);
    sum(p<<1|1)=g(p<<1|1)+tag(p);
    tag(p)=0;return;
}
inline void change(int p,int l,int r,int x)
{
    if(h(p)>=x)return;
    if(l<=l(p)&&r>=r(p))
        if(s(p)<=x)
        {
            tag(p)=x;s(p)=h(p)=x;
            sum(p)=h(p)+g(p);
            return;
        }
    if(tag(p))pushdown(p);
    int mid=(l(p)+r(p))>>1;
    if(l<=mid)change(p<<1,l,r,x);
    if(r>mid)change(p<<1|1,l,r,x);
    s(p)=max(s(p<<1),s(p<<1|1));
    h(p)=min(h(p<<1),h(p<<1|1));
    g(p)=min(g(p<<1),g(p<<1|1));
    sum(p)=min(sum(p<<1),sum(p<<1|1));
}
inline ll ask(int p,int l,int r)
{
    if(l<=l(p)&&r>=r(p))return sum(p);
    int mid=(l(p)+r(p))>>1;
    ll cnt=INF;
    if(tag(p))pushdown(p);
    if(l<=mid)cnt=min1(cnt,ask(p<<1,l,r));
    if(r>mid)cnt=min1(cnt,ask(p<<1|1,l,r));
    s(p)=max(s(p<<1),s(p<<1|1));
    h(p)=min(h(p<<1),h(p<<1|1));
    sum(p)=min(sum(p<<1),sum(p<<1|1));
    g(p)=min(g(p<<1),g(p<<1|1));
    return cnt;
}
inline void insert(int p,int x)
{
    if(l(p)==r(p)){g(p)=f[x];return;}
    int mid=(l(p)+r(p))>>1;
    if(tag(p))pushdown(p);
    if(x<=mid)insert(p<<1,x);
    else insert(p<<1|1,x);
    g(p)=min(g(p<<1),g(p<<1|1));
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=n;++i)b[i]=read(),a[i]=read();
    build(1,0,n);f[0]=0;flag=1;
    for(int i=1;i<=n;++i)
    {
        cnt+=a[i];
        while(cnt>m)++flag,cnt-=a[flag-1];
        change(1,flag-1,i-1,b[i]);
        f[i]=ask(1,flag-1,i-1);
        //cout<<f[i]<<' ';
        if(i!=n)insert(1,i);
    }
    put(f[n]);
    return 0;
}

完工~