Man Down
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 618 Accepted Submission(s): 197
Problem Description
The Game “Man Down 100 floors” is an famous and interesting game.You can enjoy the game from
http://hi.baidu.com/abcdxyzk/blog/item/16398781b4f2a5d1bd3e1eed.html
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).
Input
There are multiple test cases.
For each test case, The first line contains one integer N (2 <= N <= 100,000) representing the number of planks.
Then following N lines representing N planks, each line contain 4 integers (h,xl,xr,value)(h > 0, 0 < xl < xr < 100,000, -1000 <= value <= 1000), h represents the plank’s height, xl is the leftmost position of the plank and xr is the rightmost position. Value represents the energy the man will increase by( if value > 0) or decrease by( if value < 0) when he falls onto this plank.
Output
If the man can falls onto the floor successfully just output the maximum energy he can own when he is on the floor. But if the man can not fall down onto the floor anyway ,just output “-1”(not including the quote)
Sample Input
4
10 5 10 10
5 3 6 -100
4 7 11 20
2 2 1000 10
Sample Output
/*
题目描述:
不同高度处有不同的水平板，跳到该板会有血量变化v，
问当一个人从最高板开始，可以向左或者向右，
竖直跳到下面的板，求下落到地面的最大血量，或者-1。
线段树+dp
需要用线段树查询得到每个板的两个端点下落后会到哪个板；
然后根据这个从最高的开始dp就可以了
dp[i] = max ( dp[i], dp[i^].v ) // dp[i^] 代表能走到 i 的线段
/*
/*
Mail to : miyubai@gamil.com
Link : http://www.cnblogs.com/MiYu || http://www.cppblog.com/MiYu
Author By : MiYu
Test : 1
Complier : g++ mingw32-3.4.2
Program : HDU_3016
Doc Name : Man Down
*/
//#pragma warning( disable:4789 )
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
struct seg_tree {
int id, left, right;
int mid () { return ( left + right )>>1; }
}seg[333333];
inline void creat ( int x, int y, int rt = 1 ) {
seg[rt].left = x;
seg[rt].right = y;
//0 代表地面 其他的自然数代表各层的木板编号 -1 代表有多条线段覆盖
seg[rt].id = 0;
if ( x == y ) return ;
int mid = seg[rt].mid();
creat ( x, mid, rt << 1 );
creat ( mid + 1, y, rt << 1 | 1 );
}
inline void modify ( int x, int y, int id, int rt = 1 ) {
//找到了线段, 直接修改ID 覆盖掉
if ( seg[rt].left == x && seg[rt].right == y ) {
seg[rt].id = id;
return;
}
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
// 前面没有return掉, 那么这条线段肯定是被覆盖的, 将它的标记下传后标记为-1
if ( seg[rt].id != -1 ) {
seg[LL].id = seg[RR].id = seg[rt].id;
seg[rt].id = -1;
}
if ( y <= mid ) modify ( x, y, id, LL ); //分段修改
else if ( x > mid ) modify ( x, y, id, RR );
else {
modify ( x, mid, id, LL );
modify ( mid + 1, y, id, RR );
}
}
inline int query ( int pos, int rt = 1 ) { // 查询 Pos 所在线段的 id
if ( seg[rt].id != -1 ) return seg[rt].id; //线段被覆盖 直接返回 ID
int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
if ( pos <= mid ) return query ( pos, LL ); //分段查询
else return query ( pos, RR );
}
inline bool scan_d(int &num) //整数输入
{
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-'){ IsN=true;num=0;}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9'){
num*=10,num+=in-'0';
}
if(IsN) num=-num;
return true;
}
struct Plank {
int x,y,h,v,left,right;
//按高排序
friend bool operator < ( const Plank &a, const Plank &b ) {
return a.h < b.h;
}
}pk[100010];
int dp[100010];
int main ()
{
int N, M;
creat ( 1, 100000 );
while ( scan_d ( N ) ) {
M = -1;
for ( int i = 1; i <= N; ++ i ) {
scan_d ( pk[i].h );scan_d ( pk[i].x );scan_d ( pk[i].y );scan_d ( pk[i].v );
if ( pk[i].y > M ) M = pk[i].y; // 记录 区间最大值, 加速用的
}
modify ( 1, M, 0 );
sort ( pk + 1, pk + N + 1 ); // 按高排序
memset ( dp, 0, sizeof ( dp ) );
dp[N] = 100 + pk[N].v;
// 自底向上 更新 线段, 记录 每条线段 左右端点能到达的 线段 ID
for ( int i = 1; i <= N; ++ i ) {
int x = pk[i].left = query ( pk[i].x );
int y = pk[i].right = query ( pk[i].y );
modify ( pk[i].x, pk[i].y, i );
}
int res = -1;
//自顶向下 DP dp[i] = max ( dp[i], dp[i^].v )
// dp[i^] 代表能走到 i 的线段
for ( int i = N; i >= 1; -- i ) {
if ( dp[ pk[i].left ] < dp[i] + pk[ pk[i].left ].v )
dp[ pk[i].left ] = dp[i] + pk[ pk[i].left ].v;
if ( dp[ pk[i].right ] < dp[i] + pk[ pk[i].right ].v )
dp[ pk[i].right ] = dp[i] + pk[ pk[i].right ].v;
}
printf ( "%d\n",dp[0] > 0 ? dp[0] : -1 );
}
return 0;
}