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