|
Posted on 2010-09-08 08:57 acronix 阅读(420) 评论(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;
}

|