首页 > 其他 > 详细

P5019 铺设道路 (NOIP2018)

时间:2018-12-05 21:31:12      阅读:149      评论:0      收藏:0      [点我收藏+]

传送门

NOIP2013原题

貌似官方数据都是一模一样的

以前写过竟然毫无印象?

考场上自己瞎JB推结论

显然,如果连续的两端区间可以左边区间减 k 次,右边区间也减 k 次

那么把两个区间合并起来一起减 k 次一定是更优的

所以先考虑把整个区间拿来减几次,显然最多减的次数就是整个区间的最小值

然后此时最小值已经为零了,以最小值的位置分成左右两个区间继续同样处理就好了

如果每个区间都扫一遍最小值复杂度可以卡成 $O(n^2)$,(单调序列)

所以区间最小值容易想到ST表

然后复杂度 O(n) (每个位置对最小值只产生一次贡献)

话说官方数据 $O(n^2)$ 也能过....

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
inline int read()
{
    int 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<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int N=2e5+7;
int n,a[N],pos[N][27],Log[N];
ll ans;
void pre()//预处理ST表
{
    Log[0]=-1; for(int i=1;i<=n;i++) Log[i]=Log[i>>1]+1;
    for(int i=1;i<=n;i++) pos[i][0]=i;
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<(i-1))<=n;j++)
        {
            if(a[ pos[j][i-1] ]>a[ pos[j+(1<<(i-1))][i-1] ]) pos[j][i]=pos[j+(1<<(i-1))][i-1];
            else pos[j][i]=pos[j][i-1];
        }
}
inline int query(int l,int r)//区间求最小值
{
    int k=Log[r-l+1];
    if(a[ pos[l][k] ]>a[ pos[r-(1<<k)+1][k] ]) return pos[r-(1<<k)+1][k];
    return pos[l][k];
}
void f(int l,int r,int tot)//递归处理左右区间,tot是当前已经进行的操作次数
{
    if(l>r) return;
    int t=query(l,r);
    ans+=a[t]-tot;
    f(l,t-1,a[t]); f(t+1,r,a[t]);
}
int main()
{
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    pre();
    f(1,n,0);
    cout<<ans<<endl;
    return 0;
}

 

P5019 铺设道路 (NOIP2018)

原文:https://www.cnblogs.com/LLTYYC/p/10073429.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!