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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ2373Dividing the Path题解  

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

  下载LOFTER 我的照片书  |
                                                                     分裂道路
                                           BY   LGS
题目大意:覆盖0到L数轴的最小喷头数,每个喷头有个半径A-B范围自己可以选择,求最小覆盖区间的喷头数。还有N头奶牛,每个奶牛活动区域只能被1个喷头所覆盖。

题解:dp是N^2的,而DP的取值是一段范围内的,可以用单调队列优化。对于奶牛的干扰,直接由他们的区间+1到-1即可处理,每次入队只如不在这个区间内的,开个B[N]来记录即可。当然有某些优化:比如如果是奇数点的话直接BREAK;

总结:单调队列维护DP
代码:
  • Source Code
  • #include<cstdio>
    #define maxl 1000003
    #define maxn 2000
    #define maxx 99999999
    using namespace std;
    int h,t,i,j,n,k,m,tem,l,q,p;
    int f[maxl],w[maxl],queue[maxl];
    bool b[maxl];
    struct node{
           int l,r;
    }a[maxn];
    int main()
    {
     scanf("%d%d",&n,&l);
     scanf("%d%d",&q,&p);
     for (i=1;i<=n;i++)
       {
       scanf("%d%d",&a[i].l,&a[i].r);
       if (a[i].r-a[i].l>2*p) {
                              printf("-1");
                              return 0;
                              }
       for (j=a[i].l+1;j<=a[i].r-1;j++) b[j]=true;
       }
    for (i=1;i<=l;i++) f[i]=maxx;
    h=1;t=1;
    for (i=2*q;i<=l;i++){
               tem=i-2*q;
              while (t>h&&queue[t-1]>=f[tem])t--;
              if (!b[tem]) {queue[t]=f[tem];w[t]=tem;t++;}
              if ((i%2==1)||(b[i]))  continue;
              while (t>h&&w[h]+2*p<i) h++;
              if (t>h) f[i]=queue[h]+1;
                        }
    if (f[l]>=maxx)
    printf("-1");
     else printf("%d",f[l]);
    return 0;
    }

  评论这张
 
阅读(85)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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