40 分,求助线段树优化 DP
查看原帖
40 分,求助线段树优化 DP
394729
Weight_of_the_Soul楼主2022/9/18 19:42
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

int rd() {
    int x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-') w = -1;
        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }

    return x * w;
}

const int N = 1e6 + 5;

int n, L, R;
int dp[N];

struct Node {
    int l, r;
    int s;
}a[N];

struct Tree {
    int l, r;
    int dat;

    #define l(x) tr[x].l
    #define r(x) tr[x].r
    #define ls (p << 1)
    #define rs (ls | 1)
    #define dat(x) tr[x].dat

} tr[N << 2];

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if(l == r) {
        dat(p) = dp[l];
        return ;
    }

	int mid = (tr[p].r - tr[p].l) / 2 + tr[p].l;
    build(ls, l, mid);
    build(rs, mid + 1, r);

    dat(p) = min(dat(ls), dat(rs));
}

void change(int p, int x, int del) {
    if(l(p) == r(p)) {
        dat(p) = min(del, dat(p));
        return ;
    }
    
    int mid = (r(p) - l(p)) / 2 + tr[p].l;
    if(x <= mid) change(ls, x, del);
    if(x > mid) change(rs, x, del);

    dat(p) = min(dat(ls), dat(rs));
}

int ask(int p, int l, int r) {
    if(l <= l(p) && r(p) <= r) return dat(p);

    int res = INF;
    int mid = (tr[p].r - tr[p].l) / 2 + tr[p].l;
    if(l <= mid) res = min(res, ask(ls, l, mid));
    if(r > mid) res = min(res, ask(rs, mid + 1, r));

    return res;
}

bool cmp(Node x, Node y) {
    return x.r < y.r;
}

int main() {
    n = rd(), L = rd(), R = rd();
    for(int i = 1; i <= n; ++i)
        a[i].l = rd(), a[i].r = rd(), a[i].s = rd(), a[i].l = max(L, a[i].l), a[i].r = min(a[i].r, R);
    
    memset(dp, 0x3f, sizeof(dp));
    dp[L - 1] = 0;
    sort(a + 1, a + 1 + n, cmp);
    build(1, L - 1, R);
    
    for(int i = 1; i <= n; ++i) {
    	int mn = ask(1, a[i].l - 1, a[i].r);
    	dp[a[i].r] = min(dp[a[i].r], mn + a[i].s);
    	change(1, a[i].r, dp[a[i].r]);
    }
    
    printf("%d", dp[R] == INF ? -1 : dp[R]);
    return 0;
}
2022/9/18 19:42
加载中...