?????????? 以每個方塊左右坐標區間為節點建立字典樹，每個節點保存這個區間對應的方塊的下標，將方塊按照高度排序。

????????? 如何得到第i個方塊可以移動到的兩個方塊呢？將所有方塊排完序，將前i-1個方塊放入字典樹，根據第i個方塊的左右坐標，分別進行單點查詢即可，將下一個位置保存。

???????? 最后的DP轉移方程d[i]=max(d[i].left,d[i].right)+d[i].val；

AC代碼：

#include<cstdio> #include<algorithm> using namespace std; const int maxn=1e5+5; struct node{int l,r,ind; }tree[maxn*4]; struct point{int l,r,h,val;point(){}point(int h,int l,int r,int val):h(h),l(l),r(r),val(val){}bool operator <(const point &p)const{return h<p.h;} }plank[maxn]; void Build(int l,int r,int cur){ //建樹并初始化為floor tree[cur].l=l;tree[cur].r=r;tree[cur].ind=0;if(l==r) return;Build(l,(l+r)>>1,cur<<1);Build((l+r)/2+1,r,(cur<<1)+1); } int ind; void Insert(int l,int r,int cur){ //更新區間的值 //printf("%d %d\n",l,r);int ll=tree[cur].l,rr=tree[cur].r;if(l==ll&&r==rr) {tree[cur].ind=ind;return;}int mid=(ll+rr)>>1;if(r<=mid) Insert(l,r,cur<<1);else if(l>=mid+1) Insert(l,r,(cur<<1)+1);else {Insert(l,mid,cur<<1);Insert(mid+1,r,(cur<<1)+1);} } int val; int Search(int cur){ //搜索可以到達的下一個格子區間，返回下標 int l=tree[cur].l,r=tree[cur].r;if(l==r) return tree[cur].ind; int ind=tree[cur].ind;int mid=(l+r)>>1;int a;if(val<=mid) a=Search(cur<<1);else a=Search((cur<<1)+1);return plank[ind].h>plank[a].h?ind:a; } int main(){plank[0]=point(0,0,0,0);int n;while(scanf("%d",&n)==1){int l,r,h,v,width=-1;for(int i=1;i<=n;++i) {scanf("%d%d%d%d",&h,&l,&r,&v);width=max(width,r); plank[i]=point(h,l,r,v);}Build(1,width,1);sort(plank+1,plank+n+1); //按高度排序 for(int i=1;i<=n;++i){int l=plank[i].l,r=plank[i].r;val=l;plank[i].l=Search(1);val=r;plank[i].r=Search(1);//printf("%d %d\n",plank[i].l,plank[i].r);ind=i;Insert(l,r,1);}for(int i=1;i<=n;++i){int l=plank[i].l,r=plank[i].r;plank[i].val+=max(plank[l].val,plank[r].val);}if(plank[n].val+100<=0) printf("-1\n");else printf("%d\n",plank[n].val+100);}return 0; }
如有不當之處歡迎指出！

轉載于:https://www.cnblogs.com/flyawayl/p/8305475.html

總結

以上是生活随笔為你收集整理的hdu3016 线段树+简单DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。