Codeforces 777E Hanoi Factory(线段树维护DP)

题目链接 Hanoi Factory

很容易想到这是一个DAG模型，那么状态转移方程就出来了。

但是排序的时候有个小细节：b相同时看a的值。

因为按照惯例，堆塔的时候肯定是内半径大的在下面。

因为N有1e5，那么DP的时候用线段树优化一下，就可以了。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)              for(int i(a); i <= (b); ++i)

typedef long long LL;

const int N     =    200000      +       10;

struct Segtree{
    int l, r;
    LL num;
} segtree[N << 2];

struct node{
    int a, b;
    LL h;
    friend bool operator < (const node &A, const node &B){
        return A.b == B.b ? A.a > B.a : A.b > B.b;
    }
} c[N];

struct Node{
    int x, y;
    friend bool operator < (const Node &a, const Node &b){
        return a.x < b.x;
    }
} f[N];

int aa[N], bb[N];
int n, m, cnt;
map <int, int> mp;
LL ans;

inline void pushup(int i){
    segtree[i].num = max(segtree[i << 1].num, segtree[i << 1 | 1].num);
}

void build(int i, int l, int r){

    segtree[i].l = l;
    segtree[i].r = r;
    segtree[i].num = 0;

    if (l == r) return ;
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
}

void update(int i, int pos, LL value){
    int L = segtree[i].l, R = segtree[i].r;
    if (L == R && L == pos){
        segtree[i].num = max(segtree[i].num, value);
        return;
    }

    int mid = L + R >> 1;
    if (pos <= mid) update(i << 1, pos, value);
    else update(i << 1 | 1, pos, value);

    pushup(i);
}


LL query(int i, int l, int r){
    int L = segtree[i].l, R = segtree[i].r;
    if (L == l && R == r) return segtree[i].num;
    int mid = L + R >> 1;
    LL ret = 0;
    if (r <= mid) 
        ret = max(ret, query(i << 1, l, r));
    else 
    if (l > mid) 
        ret = max(ret, query(i << 1 | 1, l, r));
    else
    {
        ret = max(ret, query(i << 1, l, mid));
        ret = max(ret, query(i << 1 | 1, mid + 1, r));
    }

    return ret;
}


int main(){

    scanf("%d", &n);
    cnt = 0;
    rep(i, 1, n){
        scanf("%d%d%lld", aa + i, bb + i, &c[i].h);
        f[++cnt].x = aa[i];
        f[++cnt].x = bb[i];
    }

    sort(f + 1, f + cnt + 1);
    
    f[1].y = 1;
    rep(i, 2, cnt) f[i].y = f[i].x == f[i - 1].x ? f[i - 1].y : f[i - 1].y + 1;
    rep(i, 1, cnt) mp[f[i].x] = f[i].y;

    rep(i, 1, n){
        c[i].a = mp[aa[i]];
        c[i].b = mp[bb[i]];
    }

    sort(c + 1, c + n + 1);

    m = 0;
    rep(i, 1, n){
        m = max(m, c[i].a);
        m = max(m, c[i].b);
    }

    build(1, 1, m);

    rep(i, 1, n){
        LL now = query(1, 1, c[i].b - 1);
        LL cnt = now + c[i].h;
        ans = max(ans, cnt);
        update(1, c[i].a, cnt);
    }

    printf("%lld\n", ans);

    return 0;

}