Man Down
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1606 Accepted Submission(s): 571
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).
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.
题意:
游戏规则跟“是男人就下100层”一样。给出 N (2 ~ 100000)块板,每块板都有一个高度,左端值,右端值,价值。满血的时候是100,从最高那块板开始往下垂直跳落,问到达底部时候的最大值,如果总和值小于等于 0 ,则说明不能达到,则输出 -1。
思路:
线段树 + DP + 区间覆盖 + 单点查询。DP 的时候要从高往低(正向),根据板的左右端点值所在的区域来判断能到达哪一层,如果没有任何一层可以到达则说明直接到达底部,即 0 层。首先线段树预处理每块板能到达的下一层分别是什么。所以要从最低的一层开始往上覆盖(逆向),先查询左右端点分别落在哪里,再将这块板覆盖到线段树中。然后根据公式:
dp[ p[i].rl ] = max(dp[ p[i].rl ], dp[i] + p[ p[i].rl ].val);
dp[ p[i].rr ] = max(dp[ p[i].rr ], dp[i] + p[ p[i].rr ].val); 来更新值,rl,rr,代表这个板的左右端点能分别到达哪块板,dp[ i ] 代表到达这块板时候的最大值。
最后判断如果 dp [ 0 ] <= 0,则输出 -1,否则输出最大值 dp [ 0 ]。这道题的 DP 方式很像倒三角求最大和那题的 DP 方式。
注意查询的时候,当一找到有板覆盖就返回值,否则一直找,当找到 l == r 的时候依然没有板覆盖则返回 0,说明这块板直接到达底部。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 100005; typedef struct { int h, l, r, val; int rl, rr; } node; node p[MAX]; int dp[MAX]; int cover[MAX * 3]; bool cmp(node a, node b) { return a.h < b.h; } void push_down(int node, int l, int r) { if (cover[node] != -1) { cover[node << 1] = cover[node]; cover[node << 1 | 1] = cover[node]; cover[node] = -1; } } void build (int node, int l, int r) { if (l == r) { cover[node] = -1; } else { int mid = (r + l) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); cover[node] = -1; } } void updata (int node, int l, int r, int cl, int cr, int c) { if (cl > r || cr < l) return; if (cl <= l && cr >= r) { cover[node] = c; return; } push_down(node, l, r); int mid = (r + l) >> 1; if (cl <= mid) updata(node << 1, l, mid, cl, cr, c); if (cr > mid) updata(node << 1 | 1, mid + 1, r, cl, cr, c); } int query (int node, int l, int r, int c) { if (cover[node] != -1) return cover[node]; if (l == r && cover[node] == -1) return 0; push_down(node, l, r); int mid = (r + l) >> 1; if (c <= mid) return query(node << 1, l, mid, c); return query(node << 1 | 1, mid + 1, r, c); } int main() { int n; while (~scanf("%d", &n)) { int Max_r = 0; for (int i = 1; i <= n; ++i) { scanf("%d%d%d%d", &p[i].h, &p[i].l, &p[i].r, &p[i].val); Max_r = max(Max_r, p[i].r); } sort(p + 1, p + n + 1, cmp); build(1, 1, Max_r); for (int i = 1; i <= n; ++i) { p[i].rl = query(1, 1, Max_r, p[i].l); p[i].rr = query(1, 1, Max_r, p[i].r); updata(1, 1, Max_r, p[i].l, p[i].r, i); } memset(dp, -1, sizeof(dp)); dp[n] = 100 + p[n].val; for (int i = n; i >= 1; --i) { dp[ p[i].rl ] = max(dp[ p[i].rl ], dp[i] + p[ p[i].rl ].val); dp[ p[i].rr ] = max(dp[ p[i].rr ], dp[i] + p[ p[i].rr ].val); } if (dp[0] <= 0) printf("-1\n"); else printf("%d\n", dp[0]); } return 0; }
相关推荐
man文件(busubox+mksh+linux_shell编程if中参数)
开源项目-driusan-mandown.zip,mandown: a tool to help write man pages in markdown
树型DP和状态压缩DP+acm.ppt
notpad++64位的插件,解压后将文件复制到notpad++的插件目录下就可以使用了
MAN+B&W+主机FIVA+故障诊断分析.doc
使用C ++和SFML制作的Pac-Man游戏克隆。描述:游戏由一个包含点,超级点和奖励水果的迷宫组成。玩家的目标是在吃豆人中穿越迷宫并收集所有点,而不会被鬼魂抓到。特征:记分板显示前10个得分具有挑战性的游戏体验,...
炸弹人 C ++中的Bomberman游戏(学校项目)
X-Man后台管理框架Author XinyLayui2.4.3+Thinkphp3.2.3后台管理框架,一键增删改查,支持多表外联,控件多样化,完善的权限管理模块演示地址:如果觉得对你有所帮助 请为我点个星星 谢谢数据库文件 xinyadmin.sql如...
x-man系列地图不用介绍了吧。下面是地图列表 x-man2003 x-man2003.bsp X-man2003b.bsp x-man2004b.bsp x-man2004c.bsp X-man2006.bsp X-man2007.bsp X-man2008.bsp X-man2009.bsp X-man2010.bsp X-man2011Benladen....
爬虫-Spiderman+WebCollector Spiderman2 Web Collector Spiderman2 WebCollector 爬虫-Spi derman+WebCollector 爬虫-Spiderman+WebColl ector 爬虫-Spiderman+WebCollector 爬虫-Spide rman+WebCollector
Notepad++ sql格式化插件 Poor Man's T-SQL Formatter SqlFormatterNppPlugin.1.5.1
人月神话 the mythical man month 中文版和英文版都有
炸弹人 一个用C ++编写的具有ECS设计和用OpenGL实现的图形的3D轰炸机致敬游戏。 包含8个级别,可播放4个主题。 入门 ... 建造 make deps make ... 文献资料 要求: doxygen >= 1.8.4 Python 3.6例如在MacOS上。...
Freeman-Durden极化分解代码
Linux中文man在线手册 Linux中文man在线手册 Linux中文man在线手册 Linux中文man在线手册
介绍MAN是用C ++ 17编写的ThreadPool。 之所以选择这个名称,是因为至少在法国,据说男人不能同时做几件事。不同的阶级可运行的介绍类Runnable的定义如下: class Runnable ; Args...是要赋予Runnable::operator();...
强人strongMan是StrongSwan的管理界面。 StrongMan基于Django和Python,提供了一个用户友好的图形界面来配置和建立IPsec连接。 它支持RSA / ECDSA非对称加密带有用户名和密码的EAP EAP-TLS 服务器认证回合StrongMan...
学习linux离不开学习那些命令,学习命令看man page手册是好方法。 但原版的man page是英文版的,对于像我这样英语还很菜的新手来说是不小的难题。 就找了这个中文版的man手册 安装: 1.下载中文man压缩包 ...
Linux程序员man手册
社区二手跳蚤市场小程序 superman_hand2 5.4.10带支付+上架通知+广告插件.rar