hdu 3016 Man Down(简单线段树&简单DP)

Man DownTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1410 Accepted Submission(s): 492


Problem Description
We take a simplified version of this game. We have only two kinds of planks. One kind of the planks contains food and the other one contains nails. And if the man falls on the plank which contains food his energy will increase but if he falls on the plank which contains nails his energy will decrease. The man can only fall down vertically .We assume that the energy he can increase is unlimited and no borders exist on the left and the right.

First the man has total energy 100 and stands on the topmost plank of all. Then he can choose to go left or right to fall down. If he falls down from the position (Xi,Yi),he will fall onto the nearest plank which satisfies (xl <= xi <= xr)(xl is the leftmost position of the plank and xr is the rightmost).If no planks satisfies that, the man will fall onto the floor and he finishes his mission. But if the man’s energy is below or equal to 0 , he will die and the game is Over.

Now give you the height and position of all planks. And ask you whether the man can falls onto the floor successfully. If he can, try to calculate the maximum energy he can own when he is on the floor.(Assuming that the floor is infinite and its height is 0,and all the planks are located at different height).InputOutputSample InputSample OutputSourceRecommend#include<algorithm>#include<iostream>#include<string.h>#include<sstream>#include<stdio.h>#include<math.h>#include<vector>#include<string>#include<queue>#include<set>#include<map>using namespace std;const int INF=0x3f3f3f3f;const int maxn=100010;int dp[maxn],id[maxn<<2],li[maxn],ri[maxn];struct node{ int h,xl,xr,val;} plan[maxn];bool cmp(node a,node b){ return a.h<b.h;}void btree(int L,int R,int k){ int ls,rs,mid; id[k]=0; if(L==R) return ; ls=k<<1; rs=ls|1; mid=(L+R)>>1; btree(L,mid,ls); btree(mid+1,R,rs);}void pushdown(int k){ int ls,rs; ls=k<<1; rs=ls|1; id[ls]=id[rs]=id[k]; id[k]=0;}void update(int L,int R,int l,int r,int k,int d){ int ls,rs,mid; if(l==L&&r==R) { id[k]=d; return; } if(id[k]) pushdown(k); ls=k<<1; rs=ls|1; mid=(L+R)>>1; if(l>mid) update(mid+1,R,l,r,rs,d); else if(r<=mid) update(L,mid,l,r,ls,d); else { update(L,mid,l,mid,ls,d); update(mid+1,R,mid+1,r,rs,d); }}int qu(int L,int R,int p,int k){ int ls,rs,mid; if(L==R||id[k]) return id[k]; ls=k<<1; rs=ls|1; mid=(L+R)>>1; if(p>mid) return qu(mid+1,R,p,rs); else return qu(L,mid,p,ls);}int main(){ int n,i,lim; while(~scanf("%d",&n)) { lim=0; plan[0].val=0; dp[0]=-INF; for(i=1;i<=n;i++) { scanf("%d%d%d%d",&plan[i].h,&plan[i].xl,&plan[i].xr,&plan[i].val); lim=max(lim,plan[i].xr); dp[i]=-INF; } sort(plan+1,plan+n+1,cmp); btree(1,lim,1); for(i=1;i<=n;i++) { li[i]=qu(1,lim,plan[i].xl,1); ri[i]=qu(1,lim,plan[i].xr,1); update(1,lim,plan[i].xl,plan[i].xr,1,i); } dp[n]=100+plan[n].val; for(i=n;i>=1;i--) { if(dp[i]>0)//题目数据有点水。不加这个判断也能过。 { dp[li[i]]=max(dp[li[i]],dp[i]+plan[li[i]].val); dp[ri[i]]=max(dp[ri[i]],dp[i]+plan[ri[i]].val); } } if(dp[0]<=0) dp[0]=-1; printf("%d\n",dp[0]); } return 0;}/*45 2 6 1004 1 4 -2003 5 8 -2002 1 10 50025 2 6 1004 1 4 -200*//*-1//数据水了。不是-1也行。100*/