注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ2374Fence Obstacle Course题解  

2014-03-25 21:44:12|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                  围栏
                                         BY   LGS
题目大意:有N段栅栏,牛们一开始在第N个栅栏行里,X坐标给定。每次牛可以往下走直到遇到栅栏,然后选择向左或者向右行走,直到到端点,然后再往下走。求走到最后原点的最短X轴行走距离。

题解:DP表示做到第I个栅栏F[I][0..1]左端点、右端点走到原点的最短距离。那么答案就在MAX(F[N][0]+ABS(L[N]-X0),F[N][1]+ABS(R[N]-X0));然而如果对于第i个线段,先考虑左端点,他下面没有线段,那距离就是ABS(L[I]),如果有,设为K。那么F[I][0]=MIN(F[I][0]+ABS(L[K]-L[I]),F[I][1]+ABS(R[K]-L[I]));右端点类似然而如何确定i个线段下面第一次遇到的线段k呢,这里便需要用到线段树维护。这个很像火烧赤壁,线段树维护区间覆盖问题,个人感觉比较水的。每次做完I,就插入到线段树中,覆盖颜色。
当然,我用了LAZY思想写线段树。

总结:线段树+DP;
代码:
  • Source Code
  • #include<cstdio>
    #include<algorithm>
    #define maxn 100000
    #define maxx 29999999
    #define L 900001
    using namespace std;
    int flag,i,j,k,n,x0,ans,t,m,w,l,r;
    int f[maxn][2];
    struct node{int l,r,cover,lazy;}tree[L];
    struct node2{int l,r;}a[maxn];
    int abs(int a){return (a>0)?a:(-a);}
    int min(int a,int b){return (a>b)?b:a;}
    void down(int tot)
     {
     int w=tree[tot].lazy;
     tree[tot*2].cover=tree[tot*2+1].cover=tree[tot*2].lazy=tree[tot*2+1].lazy=w;
     tree[tot].lazy=0;
     }
    void insert(int l,int r,int tot)
     {
     if (l==tree[tot].l&&r==tree[tot].r){
              tree[tot].cover=i;
              tree[tot].lazy=i;
                                  return;
                                  }
     if (tree[tot].lazy!=0) down(tot);
     int mid=(tree[tot].l+tree[tot].r)/2;
     if (r<=mid) insert(l,r,tot*2);
      else if (l>mid) insert(l,r,tot*2+1);
       else {
            insert(l,mid,tot*2);
            insert(mid+1,r,tot*2+1);
            }
     }
    void find(int w,int tot)
     {
     if (w==tree[tot].l&&w==tree[tot].r) {j=tree[tot].cover;return;}
     if (tree[tot].lazy!=0) down(tot);
     int mid=(tree[tot].l+tree[tot].r)/2;
     if (w<=mid) find(w,tot*2);
       else find(w,tot*2+1);
     }
    void build(int a,int b,int tot)
     {
     tree[tot].l=a;tree[tot].r=b;
     if (a==b) return;
     int mid=(a+b)/2;
     build(a,mid,tot*2);build(mid+1,b,tot*2+1);
     }
    int main()
    {
       scanf("%d%d",&n,&x0);l=0;r=200000;x0+=100000;
      for (i=1;i<=n;i++) {scanf("%d%d",&a[i].l,&a[i].r);
                         a[i].l+=100000;a[i].r+=100000; 
                         }
      for (i=0;i<=n;i++)f[i][0]=f[i][1]=maxx;
                     
      build(l,r,1);
      for (i=1;i<=n;i++)
           {
           j=0;
           find(a[i].l,1);
           if (j!=0){
    f[i][0]=min(f[j][0]+a[i].l-a[j].l
               ,f[j][1]+a[j].r-a[i].l);
                       }
                  else f[i][0]=abs(a[i].l-100000);
                     
           j=0;
           find(a[i].r,1);
           if (j!=0){
    f[i][1]=min(f[j][0]+a[i].r-a[j].l
               ,f[j][1]+a[j].r-a[i].r);
                       } 
                 else f[i][1]=abs(a[i].r-100000);
           
            insert(a[i].l,a[i].r,1);
           }   
         ans=min(f[n][0]+abs(x0-a[n].l),f[n][1]+abs(a[n].r-x0));
         printf("%d\n",ans);
    return 0;
    }
                              
  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018