Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

线段树优化DP,AC留念,留下源码

Posted by vjubge4 at 2019-05-25 13:37:13 on Problem 3171
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson rt << 1
#define rson rt << 1 | 1
using namespace std;

const int oo = 0x3f3f3f3f;
int N, S, T;
struct Node {
    int from, to, cost;
} nodes[10000];
int dp[86400];

bool comp(Node a, Node b) {
    if(a.from == b.from) {
        return a.to < b.to;
    }
    return a.from < b.from;
}

int ST[86400 << 2];

void Push_Up(int rt) {
    ST[rt] = min(ST[lson], ST[rson]);
}

void Update(int L, int R, int k, int l, int r, int rt) {
    if(l == r) {
        ST[rt] = k;
        return;
    }
    int m = (l + r) >> 1;
    if(L <= m) {
        Update(L, R, k, l, m, lson);
    }
    if(m < R) {
        Update(L, R, k, m + 1, r, rson);
    }
    Push_Up(rt);
}

int Query(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) {
        return ST[rt];
    }
    int m = (l + r) >> 1;
    int MI = oo;
    if(L <= m) {
        MI = min(MI, Query(L, R, l, m, lson));
    }
    if(m < R) {
        MI = min(MI, Query(L, R, m + 1, r, rson));
    }
    return MI;
}

int main() {
    scanf("%d %d %d", &N, &S, &T);
    T ++;
    for(int i = 0; i < N; i ++) {
        scanf("%d %d %d", &nodes[i].from, &nodes[i].to, &nodes[i].cost);
        nodes[i].to ++;
    }
    sort(nodes, nodes + N, comp);
    memset(dp, oo, sizeof(dp));
    memset(ST, oo, sizeof(ST));
    dp[S] = 0;
    Update(S, S, 0, 0, T, 1);
    for(int i = 0; i < N; i ++) {
        int pre_cost = Query(nodes[i].from, nodes[i].to, 0, T, 1);
        if(dp[nodes[i].to] > pre_cost + nodes[i].cost) {
            dp[nodes[i].to] = pre_cost + nodes[i].cost;
            Update(nodes[i].to, nodes[i].to, dp[nodes[i].to], 0, T, 1);
        }
    }
    if(dp[T] == oo) {
        printf("-1\n");
    } else {
        printf("%d\n", dp[T]);
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator