Man Down
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1410Accepted Submission(s): 492
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
Source
Recommend
gaojie
题意:
题目是以"是男人就下一百层"游戏为背景。不过加以简化了。就说只有两种木板了。一种到达上面后可以得到上面的分数。另一种就减相应的分数。每一个木板会给你它的左右端点的坐标。[xl,xr]。然后小人会到达高度比当前木板低。
且满足。xl'<=xl<=xr'或。xl'<=xr<=xr'。的最近木板上。因为它只能从当前木板的左边或右边下去嘛。
如果不存在这样的木板。他就完成了它的使命。(因为玩过这个游戏的缘故我开始以为他挂掉了然后wa了数次)
还有如果中途分数小于或等于0的话那么它就挂掉了。初始分为100.
思路:
由于这是在线段树专题里找的题。于是拼命往线段树上想。白白YY那么久。其实这题就是一简单DP因为对于一个木板要么从左边下去。要么从右边下去。但由于高度不连续所以处理有点不同。这题关键在处理最近上。我们可以用一颗线段树来维护。先把木板高度按高度升序排序。然后对于当前木板。查一下它左右端点被谁覆盖了用数组记录下来。因为是升序排序的。查到的一定是最近的。然后再用这木板去覆盖点。循环做。我开始想着从终点倒着走回去
就不用记录了。但发现有bug。因为有可能存在正这走挂了。倒着走不挂的情况。
4
5 2 6 100
4 1 4 -200
3 5 8 -200
2 1 10 500
所以只能走。
详细见代码:
#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;
}
/*
4
5 2 6 100
4 1 4 -200
3 5 8 -200
2 1 10 500
2
5 2 6 100
4 1 4 -200
*/
/*
-1//数据水了。不是-1也行。
100
*/
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
HDU的一题........HDU DP动态规
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
NULL 博文链接:https://128kj.iteye.com/blog/1738772
动态规划DP题解 POJ HDU部分动态规划DP题解
hdu 1005.比较简单的一道题,有兴趣的可以看看。
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
hdu ACM 各种排序
HDU1059的代码