题解 P2101 【命运石之门的选择】

· · 题解

石头门厨前来报到。

题解里面似乎都是 O(n^2) 的？

这里提供一个 O(n \log n) 的做法。

原题

首先，每次要么出现横涂，要么全是竖涂；而如果出现横涂，先横涂再竖涂一定不会劣于先竖涂再横涂。

其次，横涂先涂最底层也不会劣于后涂最底层。因为早晚都要涂掉最底层。

再次，每次涂如果是横涂，必然是一口气做掉当前最矮的矩形并消掉能消掉的部分。

原因：如果不把最矮的消完，横涂就跟没涂一样，因为列数不变，剩下的还是要一列一列涂过去。而且，我们是先涂最底层的。

那么做法就很明显了：每次涂可以出现横涂，此时可以把该部分中最矮的横涂掉，再把该部分所有矩形高度减掉最矮的部分，接着递归计算被涂掉的部分左右两边所需时间。

而如果不出现横涂，那么有几列要涂就要几步。

比较二者大小，取较小值即为答案。

到这里，已经可以 O(n^2) 按上述过程模拟解决了。

但是抱着对助手石头门深切的热爱，我决定优化复杂度。

观察上述过程：每次尝试横涂时，必然消掉一列，也就是函数最多会被调用 n 次。

然后我们要找最小值，以及区间修改。这可以用线段树做到 \log n 。

于是加个线段树上去就好了。

代码里有注释，希望能解答您的疑惑。

#include <cstdio>
#include <cstdlib>

const int maxn=1e5+5;const int inf=1e9+7;

template<typename T>
inline T min(T a,T b){
    return a<b?a:b;
}

template<typename T1=int,typename T2=int>
struct pair{
    T1 ft;T2 sd;
    pair():ft(),sd(){}
    pair(T1 _ft,T2 _sd):ft(_ft),sd(_sd){}
    bool operator<(const pair _Tp)const{
        if(sd!=_Tp.sd) return sd<_Tp.sd;
        return ft<_Tp.ft;
    }
};

int n,a[maxn];

struct Sgt{
    struct node{
        #define null 0
        node *l,*r;pair<> minn;int tag;
        node(){
            l=r=null;tag=0;
        }
        void push_up(){
            if(!l&&!r) return;
            minn=min(l->minn,r->minn);
        }
        void push_down(){
            if(!l&&!r) return;
            if(tag){
                l->tag+=tag;l->minn.sd+=tag;
                r->tag+=tag;r->minn.sd+=tag;
                tag=0;
            }
        }
    }*rt,*pt;
    void init(int Size){pt=(node*)malloc(sizeof(node)*Size*2);}
    node* build(int l,int r){
        node *now=pt++;
        if(l==r){
            now->minn=pair<>(l,a[l]);
            return now;
        }
        int mid=(l+r)>>1;
        now->l=build(l,mid),now->r=build(mid+1,r);
        return now->push_up(),now;
    }
    pair<> wonder_minn(int _l,int _r,node *now,int l,int r){
        if(r<_l||l>_r) return pair<>(004,inf);
        if(_l<=l&&r<=_r) return now->minn;
        now->push_down();int mid=(l+r)>>1;
        return min(wonder_minn(_l,_r,now->l,l,mid),wonder_minn(_l,_r,now->r,mid+1,r));
    }
    void modify(int _l,int _r,node *now,int l,int r,int tag){
        if(r<_l||l>_r) return;
        if(_l<=l&&r<=_r){
            now->tag+=tag,now->minn.sd+=tag;
            return;
        }
        now->push_down();int mid=(l+r)>>1;
        modify(_l,_r,now->l,l,mid,tag),modify(_l,_r,now->r,mid+1,r,tag);
        return now->push_up();
    }
}s;
//为什么要用指针？胸针让我这么干的，据说是为了迷惑机关

int Sg(int l,int r){//第l根柱子到第r根柱子
    int answer=r-l+1;
    pair<> ChrisTina=s.wonder_minn(l,r,s.rt,1,n);//最小值
    if(ChrisTina.sd>=answer) return answer;
    if(ChrisTina.sd) s.modify(l,r,s.rt,1,n,-ChrisTina.sd);
    return min(answer,ChrisTina.sd+Sg(l,ChrisTina.ft-1)+Sg(ChrisTina.ft+1,r));
    //也许你会好奇，同时是最小值的柱子有可能不止一个，于是会弄出来0，导致横消不能
    //但是无妨，那样ChrisTina会找到0，然后递归左右两边，这样就会自动把0给分开
}

int main(){
    scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    s.init(n);s.rt=s.build(1,n);
    printf("%d\n",Sg(1,n));
    return 0;
}

然后因为常数感人并跑不过 O(n^2) 。