题目链接:hdu 3016 Man Down
题目大意:有N个板,每个板有高度,以及l,r,d,l和r表示所在区间,d表示跳到该板上后将获得的能量(可能为负),保证没有两个板的高度相同。人的初始位置为最高的板上,能量值为100,如果能量值为0则game over,每次可以从左边或者右边跳下去,每次跳越属于垂直下落,落到最近的板上。求移动到地面上后的最大能量值,地面高度为0并且长度视为无穷大。
解题思路:用线段树成段更新,每个位置表示从该点下落时的能量值,线段树维护最大值。将板按照高度从大到小排序,每次查询l,r区间中的最大值x,然后将l+1,r-1修改成不能移动,l,r则修改成x+v(v为对应板的权值),注意过程中死亡的情况。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
const int INF = 0x3f3f3f3f;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2], v[maxn << 2], s[maxn << 2];
inline void maintain(int u, int d) {
v[u] = s[u] = d;
}
inline void pushup (int u) {
s[u] = max(s[lson(u)], s[rson(u)]);
}
inline void pushdown(int u) {
if (v[u]) {
maintain(lson(u), v[u]);
maintain(rson(u), v[u]);
v[u] = 0;
}
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
v[u] = s[u] = -INF;
if (l == r)
return;
int mid = (l + r) / 2;
build (lson(u), l, mid);
build (rson(u), mid + 1, r);
pushup(u);
}
void modify (int u, int l, int r, int d) {
if (l <= lc[u] && rc[u] <= r) {
maintain(u, d);
return;
}
pushdown(u);
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
modify(lson(u), l, r, d);
if (r > mid)
modify(rson(u), l, r, d);
pushup(u);
return;
}
int query(int u, int l, int r) {
if ((l <= lc[u] && rc[u] <= r) || v[u])
return s[u];
pushdown(u);
int mid = (lc[u] + rc[u]) / 2, ret = -INF;
if (l <= mid)
ret = max(ret, query(lson(u), l, r));
if (r > mid)
ret = max(ret, query(rson(u), l, r));
pushup(u);
return ret;
}
struct plank {
int h, l, r, d, v;
void read () {
scanf("%d%d%d%d", &h, &l, &r, &d);
}
friend bool operator < (const plank& a, const plank& b) {
return a.h > b.h;
}
}p[maxn+5];
int N;
int main () {
while (scanf("%d", &N) == 1) {
build (1, 1, maxn);
for (int i = 1; i <= N; i++)
p[i].read();
sort(p + 1, p + N + 1);
p[1].v = 100 + p[1].d;
modify(1, p[1].l, p[1].r, -INF);
if (p[1].v > 0) {
modify(1, p[1].l, p[1].l, p[1].v);
modify(1, p[1].r, p[1].r, p[1].v);
}
for (int i = 2; i <= N; i++) {
int ret = query(1, p[i].l, p[i].r);
p[i].v = ret + p[i].d;
modify(1, p[i].l, p[i].r, -INF);
if (p[i].v > 0) {
modify(1, p[i].l, p[i].l, p[i].v);
modify(1, p[i].r, p[i].r, p[i].v);
}
}
int ans = query(1, 1, maxn);
printf("%d\n", ans <= 0 ? -1 : ans);
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
题面 【题目描述】 有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的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。