|
Posted on 2010-09-08 08:57 acronix 阅读(407) 评论(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;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct node {
int l,r,c;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct node tree[400100];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void build(int l,int r,int v) {
tree[v].c=0;
tree[v].l=l;
tree[v].r=r;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(l==r) {
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int mid=(l+r)>>1;
build(l,mid,v<<1);
build(mid+1,r,(v<<1)+1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void insert(int pos,int n,int v) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(tree[v].l==tree[v].r) {
if(n>tree[v].c)
tree[v].c=n;
return;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int mid=(tree[v].l+tree[v].r)>>1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(pos>mid) {
insert(pos,n,(v<<1)+1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
insert(pos,n,v<<1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tree[v].c=max(tree[v<<1].c,tree[(v<<1)+1].c);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int find(int l,int r,int v) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(tree[v].l==l&&tree[v].r==r) {
return tree[v].c;
}
int mid=(tree[v].l+tree[v].r)>>1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(l>mid) {
return find(l,r,(v<<1)+1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else if(r<=mid) {
return find(l,r,v<<1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
return max(find(l,mid,v<<1),find(mid+1,r,(v<<1)+1));
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) struct box {
int h,g;
};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct box boxes[100010];
int num[100010],dp[100010];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int b_search(int n,int u) {
int l=1,r=n;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(l<=r) {
int mid=(l+r)>>1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(num[mid]==u) {
return mid;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else if(num[mid]>u) {
r=mid-1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
l=mid+1;
}
}
return -1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int n,maxg;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d",&n)!=EOF) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=1;i<=n;i++) {
scanf("%d %d",&boxes[i].h,&boxes[i].g);
num[i]=boxes[i].h;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sort(num+1,num+n+1);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int index=1;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=2;i<=n;i++) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(num[index]!=num[i]) {
index++;
num[index]=num[i];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
build(1,index,1);
dp[1]=boxes[1].g;
insert(b_search(index,boxes[1].h),dp[1],1);
maxg=dp[1];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(int i=2;i<=n;i++) {
int end=b_search(index,boxes[i].h);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(end-1==0) {
dp[i]=boxes[i].g;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
dp[i]=find(1,end-1,1)+boxes[i].g;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
insert(end,dp[i],1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(dp[i]>maxg) {
maxg=dp[i];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d\n",maxg);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|