posts - 64, comments - 4, trackbacks - 0, articles - 0

hdu_3607(dp+离散化+线段树)

Posted on 2010-09-08 08:57 acronix 阅读(403) 评论(0)  编辑 收藏 引用 所属分类: zhaoboqiang解题报告

      首先将箱子的高度进行离散化处理,然后根据箱子的高度建树,dp[i]=max(dp[j])+gi(1<=j<i且hi>hj),通过线段树查找小于hi的dp[j]最大值,即查找1到hi-1之间的最大值。结果是dp[i]的最大值。线段树应用还是很神奇的o(∩_∩)o

#include<stdio.h>
#include
<algorithm>
using namespace std;

struct node{
    
int l,r,c;
}
;

struct node tree[400100];

void build(int l,int r,int v){
    tree[v].c
=0;
    tree[v].l
=l;
    tree[v].r
=r;
    
if(l==r){
        
return;
    }


    
int mid=(l+r)>>1;
    build(l,mid,v
<<1);
    build(mid
+1,r,(v<<1)+1);
}


void insert(int pos,int n,int v){
    
if(tree[v].l==tree[v].r){
        
if(n>tree[v].c)
            tree[v].c
=n;
        
return;
    }


    
int mid=(tree[v].l+tree[v].r)>>1;

    
if(pos>mid){
        insert(pos,n,(v
<<1)+1);
    }
else{
        insert(pos,n,v
<<1);
    }


    tree[v].c
=max(tree[v<<1].c,tree[(v<<1)+1].c);
}


int find(int l,int r,int v){
    
if(tree[v].l==l&&tree[v].r==r){
        
return tree[v].c;
    }

    
int mid=(tree[v].l+tree[v].r)>>1;

    
if(l>mid){
        
return find(l,r,(v<<1)+1);
    }
else if(r<=mid){
        
return find(l,r,v<<1);
    }
else{
        
return max(find(l,mid,v<<1),find(mid+1,r,(v<<1)+1));
    }

}


struct box{
    
int h,g;
}
;

struct box boxes[100010];
int num[100010],dp[100010];

int b_search(int n,int u){
    
int l=1,r=n;
    
while(l<=r){
        
int mid=(l+r)>>1;
        
if(num[mid]==u){
            
return mid;
        }
else if(num[mid]>u){
            r
=mid-1;
        }
else{
            l
=mid+1;
        }

    }

    
return -1;
}



int main(){
    
int n,maxg;
    
while(scanf("%d",&n)!=EOF){
        
for(int i=1;i<=n;i++){
            scanf(
"%d %d",&boxes[i].h,&boxes[i].g);
            num[i]
=boxes[i].h;
        }


        sort(num
+1,num+n+1);

        
int index=1;
        
for(int i=2;i<=n;i++){
            
if(num[index]!=num[i]){
                index
++;
                num[index]
=num[i];
            }

        }


        build(
1,index,1);
        dp[
1]=boxes[1].g;
        insert(b_search(index,boxes[
1].h),dp[1],1);
        maxg
=dp[1];
        
for(int i=2;i<=n;i++){
            
int end=b_search(index,boxes[i].h);

            
if(end-1==0){
                dp[i]
=boxes[i].g;
            }
else{
                dp[i]
=find(1,end-1,1)+boxes[i].g;
            }


            insert(end,dp[i],
1);
            
if(dp[i]>maxg){
                maxg
=dp[i];
            }

        }


        printf(
"%d\n",maxg);
    }

    
return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理