HDU 3016 （Man Down）线段树+简单dp

题目大意：就是一个man从 最高处的横木往下跳，在这里与我们平时的游戏有点出入，在此处 我们只能往最近的，并且包含我左或右端点的一个横木区间上跳。man的初始血量为100，每跳到一个横木上他的血量都有可能发生变化，当横木上放着食物的时候，man的血回increase，如果是障碍之类的就损耗血量。

题目分析：在这里我们要处理的问题只有两个：1）如何才能找到包含当前区间的左，右端点的最近 的区间  2）如何跳才能剩下最多血量到达地面。

解决方案：首先按横木高度 进行升序排序，然后从低往高 进行插入，并且 查询包含其左或者右端点的 最近的 下面的区间：查找每块木板左边和右边的木板时只需要在线段树上找左边和右边坐标被谁覆盖就好了；

然后就是选择最优的操作方案：dp方程：dp[left]=max(dp[left],dp[i]+w[left]);  在这里详细的解释一下各个变量的 实际意义：dp[left]是指没有经过第i块横木 跳下来的的方案的血量，dp[i]表示跳到第i个横木所剩下的血，w[left]是指left这个横木上所消耗的血，dp[i]+w[left]是指经过第i个横木然后跳到left上的方案，dp方程就是为了 在这两大类方案中选择最优的！！

代码如下：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;

struct TREE{
	int a,b;
	int color;
}tree[300000];

struct node{
	int x,y,h;
	int left,right,w;
}s[300000];

int dp[100000];

int cmp(struct node a,struct node b){
	return a.h<b.h;
}

int Build(int x,int y,int num){
	tree[num].a=x;	tree[num].b=y;
	tree[num].color=0;
	if(x==y)
		return 0;
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid+1,y,num+num+1);
}

int modify(int x,int y,int num,int flag){
	if(x<=tree[num].a&&y>=tree[num].b){
		tree[num].color=flag;
		return 0;
	}
	if(tree[num].color!=-1){
		tree[num+num+1].color=tree[num+num].color=tree[num].color;
		tree[num].color=-1;
	}
	int mid=(tree[num].a+tree[num].b)/2;
	if(x<=mid)
		modify(x,y,num+num,flag);
	if(y>=mid+1)
		modify(x,y,num+num+1,flag);
}

int search(int pos,int num){
	if(tree[num].color!=-1)
		return tree[num].color;
	int mid=(tree[num].a+tree[num].b)/2;
	if(pos<=mid)
		search(pos,num+num);
	else if(pos>=mid+1)
		search(pos,num+num+1);
}

int main(){
	int i,n,maxn;
	Build(1,100000,1);
	while(scanf("%d",&n)!=EOF){
		maxn=0;
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++){
			scanf("%d %d %d %d",&s[i].h,&s[i].x,&s[i].y,&s[i].w);
			if(maxn<s[i].y)
				maxn=s[i].y;
		}
		modify(1,maxn,1,0);
		sort(s+1,s+1+n,cmp);
		for(i=1;i<=n;i++){
			s[i].left=search(s[i].x,1);
			s[i].right=search(s[i].y,1);
			modify(s[i].x,s[i].y,1,i);
		}
		dp[n]=100+s[n].w;
		for(i=n;i>=0;i--){
			if(dp[i]>0){//在这里如果dp[i]小于等于0就是说经过i块横木是不明智的选择，就直接忽略掉了！！
				dp[s[i].left]=max(dp[s[i].left],dp[i]+s[s[i].left].w);
				dp[s[i].right]=max(dp[s[i].right],dp[i]+s[s[i].right].w);
			}
		}
		if(dp[0]>0)
			printf("%d\n",dp[0]);
		else
			printf("-1\n");
	}
	return 0;
}