Man Down 解题报告（hdu3016 动态规划 线段树 排序）

2018-05-30

http://acm.hdu.edu.cn/showproblem.php?pid=3016

本文迁移自老博客，原始链接为 https://lookas2001.com/man-down-%e8%a7%a3%e9%a2%98%e6%8a%a5%e5%91%8a/

算法设计

拿到题二话不说，先把这些木板按照其高从小到大排个序，然后我们给木板从下到上从1开始递增编号（我们认为最下面的地板编号为0），通过这样的一个步骤，显然，越高的木板序号越大。

根据题意，如果人在一个木板上，他只可以从这个木板的左端或者右端垂直下落。我们定义 d[i] 为当这个人到达第 i 个板的时候最大生命值。如果我们知道 d[i] 的值，我们就可以推出其左端或者右端下落到的板子相应的值。（d[j] = d[i] + 跳到 j 板上生命值的变化量）。这样，我们可以从上往下递推的求解。

但是我们如何知道这个人他在左端或者右端下落会落到哪里呢？我们可以对 x 轴根据点建立一棵线段树，然后从下往上根据木板对这个 x 轴“染色”（即对木板所覆盖的地方标记上自己的序号），这样的话，在往上推进的过程中，很方便就能求出一个木板左右端跳下去会跳到哪个板上。

示例代码

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 110000, L = 110000, INF = 0x7fffffff;

int n;

struct a_d {
    int h, l, r, v;
    int ld, rd; // left down to
} a[N];

inline bool cmp(a_d a, a_d b) {
    return a.h < b.h;
}

struct node {
    int l, r;
    int f;
    node *lc, *rc;
} mem[2 * L];
node *memp;
node *root;

node *init(int l, int r) {
    node *p = memp++;
    p->l = l;
    p->r = r;
    p->f = 0;
    if (l == r) {
        p->lc = p->rc = NULL;
    } else {
        int mid = (l + r) >> 1;
        p->lc = init(l, mid);
        p->rc = init(mid + 1, r);
    }
    return p;
}

inline void push_down(node *p) {
    if (p->f) {
        p->lc->f = p->f;
        p->rc->f = p->f;
        p->f = 0;
    }
}

void change(node *p, int l, int r, int f) {
    if (l <= p->l && p->r <= r) {
        p->f = f;
        return;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (l <= mid) change(p->lc, l, r, f);
    if (mid < r) change(p->rc, l, r, f);
}

int query(node *p, int i) {
    if (i == p->l && p->r == i) {
        return p->f;
    }

    push_down(p);
    int mid = (p->l + p->r) >> 1;
    if (i <= mid) return query(p->lc, i);
    return query(p->rc, i);
}

int d[N];

inline int max(int a, int b) {
    if (a > b) return a; else return b;
}

int main() {
//  freopen("input.txt", "r", stdin);

    while(scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) scanf("%d%d%d%d", &a[i].h, &a[i].l, &a[i].r, &a[i].v);
        a[0].v = 0;

        std::sort(a + 1, a + n + 1, cmp);
//      
//      for (int i = 1; i <= n; ++i) printf("%d %d %d\n", i, a[i].l, a[i].r); printf("\n");

        memp = mem;
        root = init(0, 100010);
        for (int i = 1; i <= n; ++i) {
//          printf("%d %d %d\n", i, a[i].l, a[i].r);
            a[i].ld = query(root, a[i].l); // 注意这里不 +1 -1
            a[i].rd = query(root, a[i].r);
            change(root, a[i].l, a[i].r, i);
        }
//      
//      for (int i = 1; i <= n; ++i) printf("%d %d %d\n", i, a[i].ld, a[i].rd);

        for (int i = 0; i <= n; ++i) d[i] = -INF;
        d[n] = 100 + a[n].v;
        for (int i = n; i; --i) {
            if (d[i] <= 0) continue;
            d[a[i].ld] = max(d[a[i].ld], d[i] + a[a[i].ld].v);
            d[a[i].rd] = max(d[a[i].rd], d[i] + a[a[i].rd].v);
        }

        if (d[0] > 0) printf("%d\n", d[0]); else printf("-1\n");
    }

    return 0;
}