首页 > 代码库 > HDU 3016 Man Down(线段树)
HDU 3016 Man Down(线段树)
HDU 3016 Man Down
题目链接
题意:是男人就下100层的游戏的简单版,每次只能从两端下落,求落地最大血量
思路:利用线段树可以处理出每个线段能来自哪几个线段,然后就是dag最长路了
代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 100005; int n; struct Line { int l, r, y, val; Line() {} Line(int l, int r, int y, int val) { this->l = l; this->r = r; this->y = y; this->val = val; } void read() { scanf("%d%d%d%d", &y, &l, &r, &val); } } line[N]; bool cmp(Line a, Line b) { return a.y < b.y; } #define lson(x) ((x<<1)+1) #define rson(x) ((x<<1)+2) struct Node { int l, r, id, lazy; void gao(int v) { lazy = v; id = v; } } node[4 * N]; void build(int l, int r, int x = 0) { node[x].l = l; node[x].r = r; node[x].id = node[x].lazy = -1; if (l == r) return; int mid = (l + r) / 2; build(l, mid, lson(x)); build(mid + 1, r, rson(x)); } void pushdown(int x) { if (node[x].lazy != -1) { node[lson(x)].gao(node[x].lazy); node[rson(x)].gao(node[x].lazy); node[x].lazy = -1; } } void add(int l, int r, int v, int x = 0) { if (node[x].l >= l && node[x].r <= r) { node[x].gao(v); return; } pushdown(x); int mid = (node[x].l + node[x].r) / 2; if (l <= mid) add(l, r, v, lson(x)); if (r > mid) add(l, r, v, rson(x)); } int query(int v, int x = 0) { if (node[x].l == node[x].r) return node[x].id; int mid = (node[x].l + node[x].r) / 2; pushdown(x); if (v <= mid) return query(v, lson(x)); if (v > mid) return query(v, rson(x)); } const int INF = 0x3f3f3f3f; int dp[N]; vector<int> g[N]; int main() { while (~scanf("%d", &n)) { build(0, 100000); line[n] = Line(0, 100000, 0, 0); for (int i = 0; i < n; i++) { line[i].read(); g[i].clear(); } n++; sort(line, line + n, cmp); for (int i = 0; i < n; i++) { if (i) { int tol = query(line[i].l); int tor = query(line[i].r); g[tol].push_back(i); if (tol != tor) g[tor].push_back(i); } add(line[i].l, line[i].r, i); } line[n - 1].val += 100; dp[n - 1] = line[n - 1].val; for (int i = n - 2; i >= 0; i--) { dp[i] = -INF; for (int j = 0; j < g[i].size(); j++) dp[i] = max(dp[i], dp[g[i][j]] + line[i].val); } if (dp[0] <= 0) dp[0] = -1; printf("%d\n", dp[0]); } return 0; }
HDU 3016 Man Down(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。