BZOJ3387栅栏行动-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

BZOJ3387栅栏行动

阅读量：6248 次

发布时间：2019-06-22

本文共 1799 字，大约阅读时间需要 5 分钟。

首先，很容易想到Dp。设f[i][0]表示第i个栅栏走左边的最短路，f[i][1]表示第i个栅栏走右边的最短路。

所以，我们要找一个刚好在第i个栅栏的左右边界下面的栅栏。如图所示：

则有：

f[i][0] = min(f[k][0] + |Left[i] - Left[k]| , f[k][1] + |Left[i] - Right[k]| )

f[i][1] = min(f[j][0] + |Right[i] - Left[j]| , f[j][1] + |Right[i] - Right[j]| )

那么，该怎样求k和j呢？

很容易想到开一个数组，从小到大覆盖。但这样的时间复杂度是O（n^2）的。用线段树区间修改，单点查询就可以了。

附上程序：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     using namespace std;typedef long long LL;#define INF 0x3fffffff#define Maxn 100010int num[Maxn<<1];int f[Maxn][2];int n,m;int a[Maxn],b[Maxn];#define L(u) u<<1#define R(u) u<<1|1struct Tnode{ int l,r; bool isset; int set;};Tnode tr[Maxn<<3];void build(int u,int l,int r){ tr[u].l = l; tr[u].r = r; tr[u].isset = true; tr[u].set = 0; if(l
                     
                      >1; build(L(u),l,mid); build(R(u),mid+1,r); }}void pushdown(int u){ if(tr[u].isset) { tr[L(u)].isset = tr[R(u)].isset = true; tr[L(u)].set = tr[R(u)].set = tr[u].set; tr[u].isset = tr[u].set = 0; }}void update(int u,int l,int r,int val){ if(l<=tr[u].l && tr[u].r<=r) { tr[u].isset = true; tr[u].set = val; return; } pushdown(u); int mid = (tr[u].l+tr[u].r)>>1; if(mid>=l) update(L(u),l,r,val); if(mid
                      
                       >1; if(p<=mid) return query(L(u),p); else return query(R(u),p);}int main(){ scanf("%d%d",&n,&m); build(1,1,Maxn<<1); a[n+1] = b[n+1] = m; for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); int k1,k2; for(int i=1;i<=n+1;i++) { k1 = query(1,a[i]+100005); k2 = query(1,b[i]+100005); f[i][0] = min(f[k1][0]+abs(a[i]-a[k1]),f[k1][1]+abs(a[i]-b[k1])); f[i][1] = min(f[k2][0]+abs(b[i]-a[k2]),f[k2][1]+abs(b[i]-b[k2])); if(a[i]+1

转载于:https://www.cnblogs.com/ouqingliang/p/9245248.html

你可能感兴趣的文章

我的友情链接

电脑系统丢失MAC地址导致无法上网的解决办法

martian source packets(ll header)

我的友情链接

我的友情链接

VMware vSphere升级笔记

想要成功，请记住！

解决Div自适应高度的方法（转）

细数国外的你必须要知道的远程工作平台

判断一个程序是c++编译还是c编译

（20120722）（笔记001）android开发基础

window.opener=null 不需确认就能关闭窗口

Spring4-松耦合实例

封装方法实现react更新元素示例

windows 2003 IIS 配置支持 CGI

mysql 多线程写入后查询丢失数据的一个bug

SQLIOSim 模拟SQLServer的行为来测试IO性能

更改activity组件切换的动画

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2025-01-09 03:50:29 当前IP: 3.15.203.195 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我