TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7845
  • 题目
  • P7845最大利润
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

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

    输入格式

    对于每一组测试数据,输入一行包含一个整数 \(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\)

    输出格式

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

    样例输入 1

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

    样例输出 1

    150

    样例输入 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

    样例输出 2

    50

    提示

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