P6727: 老师的机器人（robot）
传统题
1.000s
时间限制
128MB
内存限制
0 提交
0 解决
【题目描述】
【题目背景】
生活太难了，这不，老师刚开的饭店就倒闭了。但是生活还是要继续的。这次，老师想制作一台机器人来接金币。
【题目描述】
最近，老师意外发现了一个金矿。这个金矿非常的特殊，它竟然会自动的掉落金币。老师尝试自己接金币，但是有一点小问题。第一是老师有点老了，第二这样效率太低。为了发家致富，老师决定制作一台机器人来自动接金币。
这个金矿一共有 5
个矿道，编号为 0, 1, 2, 3, 4
。机器人只能在指定的一条直线上左右运动，同时不能离开这 5 个矿道。
一共有 n
个金币将出现在这些矿道内。老师有一种特殊能力，他能预知这 n
个金币的出现时间 t
，出现的矿道 x
和金币的价值 a
。第 i
个金币 将出现在 ti
时间，出现在编号为 xi
的矿道，对应的价值为 ai
。
老师制作的机器人开始的时候在编号为 0
的矿道，当前对应的时间为 0
。这个机器人将以单位为 1
的速度左右任意移动。 如果金币和机器人在同一时间同一矿道，机器人必将抓住该金币。机器人抓住金币的时间可以忽略不计。
请问，这样老师的机器人最多能帮助老师抓着最大的金币价值。机器人会按照最优的方案运行。
【输入格式】
从文件 robot.in
中读入数据。
输入一共包括 n + 1
行。
第 1
行为一个正整数 n
，表示一共有 n
枚金币。
其后 n
行，每行包括 3
个整数。第 i + 1
行的三个整数为 ti , xi , ai
，对
应的含义参见题目描述。
【输出格式】
输出到文件 robot.out
中。
输出包括 1
行，表示机器人能抓住的最大金币价值。
【样例 1
输入】
3
1 0 100
3 3 10
5 4 1
【样例 1
输出】
101
【样例 1
解释】
最优策略如下：
l
在编号为 0
的矿道理等待，机器人将在时间 1
接住第 1
个金币，金 币价值为 100
。
l
移动到编号为 4
的矿道，机器人将在时间 5
接住第 3
个金币，金币 价值为 1
。
这样最大的价值为 100 + 1 = 101
。
【样例 2
输入】
3
1 4 1
2 4 1
3 4 1
【样例 2
输出】
0
【样例 2
解释】
机器人接不住任何金币。
【样例 3
输入】
10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016
【样例 3
输出】
2978279323
【数据范围】
1 ≤ n ≤ 10
^5
；
0 < T1 < T2 < · · · < Tn ≤ 10
^5
；
0 ≤ xi ≤ 4
；
1 ≤ ai ≤ 10
^9
；
所有的数据都是整数，保证输入数据合法。