TouchStone
  Please Login
Login Sign Up
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P7845
  • Problem
  • P7845最大利润
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s 256MB
    Description

    现在有 \(n\) 个任务,每一个任务有一个开始时间和结束时间,同时这个任务也有一定的利润,现在想让你合理去安排这些任务的,问能获得的最大利润是多少? 注意:同一时刻只能做一个任务,一个任务结束时刻可以开始下一个任务。

    Input Format

    对于每一组测试数据,输入一行包含一个整数 \(n\),代表任务的数量 接下来 \(n\) 行,每一行输入 $3$ 个整数 \(s,t, w\) 代表每一个任务的起始时刻、终止时刻和能获得的利润。

    \(1\le n\le 10^5,1\le s,t\le 10^9,1\le w\le 10^4\)

    Output Format

    对于每一组测试数据,输出一个答案代表最大的利润

    Sample Input 1

    5
    1 3 20
    2 5 20
    3 10 100
    4 6 70
    6 9 60

    Sample Output 1

    150

    Sample Input 2

    20
    2 8 8
    16 16 8
    12 24 6
    16 24 2
    30 40 4
    24 60 8
    42 70 2
    48 64 8
    54 90 6
    20 40 4
    44 66 8
    24 120 6
    26 104 2
    112 140 10
    90 90 4
    64 64 6
    68 170 2
    108 180 10
    114 152 4
    40 200 4

    Sample Output 2

    50

    Hint

    我们选择的是第一个任务、第四个任务和第五个任务。