接苹果

admin

【问题描述】

街边有n棵苹果树排成一行， 从左至右编号1..n。

    Ti时刻, 有一个价值为Vali的苹果从编号为Qi的苹果树上落下。若你在Ti时刻正好处于该苹果树下方, 则你可以得到该苹果。

    一开始, 你可以站在任意一棵苹果树下，之后每一时刻结束, 若你站在编号为i的苹果树下, 则你在下一时刻可以站在i-2, i-1, i, i+1, i+2中任意一棵苹果树下。

    求接苹果总价值 - 你能得到的苹果的最大价值和。

【输入格式】

第一行二个整数N, M  M表示事件个数

接下来M行, 每行3个整数Ti,Qi, Vali描述一个事件, 满足没有T相同

【输出格式】

一个数, 如题意。

【输入样例】

10 5

4 6 1868

1 8 185

9 5 1450

2 1 1561

6 6 1810

【输出样例】

   1561

【数据范围】

30% N, M≤1000

50% N≤100000

100%  N≤108, M≤600000

    100%  Ti≤108,  Vali ≤104

admin

设fij表示在 时刻时位于位置i的最大收益，可以在o(mn) 的时间内解决这个问题。
换一个思路，每次不考虑下一个时刻的时候往哪里移动，而是在事件发生的时候再考虑从哪个位置移动过来。
每次事件发生的时候，就相当于从所有能转移到(Q T)的fij的中取一个最大值。
fij能转移到(QT) 的充要条件是i-j<=Q-T 或i+j>=Q+T 。
因为有效的ij一定也是事件发生的位置，那么将事件按两种方式分别排序即可确定所有可能的产生贡献的位置。
之后按照时刻枚举事件，进行前后缀查询以及单点修改，用树状数组即可实现。
复杂度为 ，可以通过。