设为首页 加入收藏

TOP

HDU 2795 Billboard（线段树点更新）
2015-07-20 17:52:39 来源: 作者: 【大 中 小】 浏览:1次
Tags：HDU 2795 Billboard 线段 更新

HDU 2795


题意：长条形广告（1*Wi），贴入广告板（h*w），尽可能的高，其次尽可能的左。


最初看到题，想到用数组记录入每一行剩余的长度，初始为w。
但是会发现每次都要从头扫描，直到找到符合的位置。时间复杂度，就不用谈了，一定T掉。


题目，又是不断更新某行的剩余长度，还要不断查询，所以线段树了。


知识点：选择范围的点更新。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #define MAXN 200001 #define PI acos(-1.0) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define bug(a) cout<<"bug---->"<
            
             >1; build(lson); build(rson); } void update(LL clen,int l,int r,int rt) { if(rlen[rt]
             
              >1; if(clen<=rlen[rt<<1]) update(clen,lson); else update(clen,rson); pushup(rt); } int main() { while(scanf("%I64d%I64d%d",&h,&w,&n)!=EOF) { int N=n; if(h
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：HDU3001 Travelling 状压DP 下一篇：hdu3572--Task Schedule(最大流+..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: