题解 P5019 【铺设道路】

The_KOG · 2018-11-13 19:48:02 · 题解

其实从考场上出来之后我的内心是懵逼的，因为dalao都说正解O(n)

那我就介绍一下我写的O(n log n)的非正解水点积分

我的想法就是对于每一个区间(l,r)存一个已铺值w,找到最小值ai,然后ans+=ai-w(铺路),然后找(l,i-1)和(i+1,r),其已铺值为ai

考场上一开始想到线段树,但是觉得有点麻烦 码力不够

然后就想到rmq+dfs,代码如下:

#include<bits/stdc++.h>
#define N 100100
#define int long long
using namespace std;
int n,ans,a[N],rmq[N][17],Lg[N];
void build(){//rmq预处理
    Lg[0]=-1;
    for(int i=1;i<=n;i++)Lg[i]=Lg[i>>1]+1,rmq[i][0]=i;
    for(int j=1;j<=Lg[n];j++){
        for(int i=1;i<=n-pow(2,j-1);i++){
            int ls=rmq[i][j-1],rs=rmq[i+(int)pow(2,j-1)][j-1];
            if(a[ls]<a[rs])rmq[i][j]=ls;
            else rmq[i][j]=rs;
        }
    }
}
int query(int l,int r){//rmq查询
    int lg2=Lg[r-l+1];
    int ls=rmq[l][lg2],rs=rmq[r-(int)pow(2,lg2)+1][lg2];
    if(a[ls]<a[rs])return ls;
    else return rs;
}
void dfs(int l,int r,int v){//查询区间(l,r),已铺值为v
    if(l>r)return;
    int mid=query(l,r);
    if(l==r){
        ans+=a[l]-v;
        return;
    }
    ans+=a[mid]-v;//铺路代价
    dfs(l,mid-1,a[mid]);//查左边(l,i-1),已铺值为a[i]
    dfs(mid+1,r,a[mid]);//查右边(i+1,r),已铺值为a[i]
}
signed main(){
//  freopen("road.in","r",stdin);
//  freopen("road.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    build();
    dfs(1,n,0);
    printf("%lld\n",ans);
    return 0;
}