把“时间” 离散成秒,用**分层 DP(按时间推进)**解决。
设 f[x][k]
表示“上一秒末”站在位置 x
,剩余定身时间为 k
(0..3
)时的最大得分。
t + y
落地。把所有得分球在该时刻该位置的分数累加到 score[t+y][x]
;若该处有任意一个非篮球,则 block[t+y][x]=True
。t
):
你正在篮球场上与其他玩家玩一场游戏。你需要站在看台边,用推车接住从看台上扔下来的篮球。
篮球上标有不同的积分,你接到后就获得了对应的积分。但是
其中有一部分玩家他们会扔其他种类的球,如果你不小心接到了
这些球,你就需要停在原地3秒。期间你只能等待时间过去,或者正好有球进入车筐中。如果你在停止期间又接到了非篮球的球类,不论之前你的停止时间还剩多少,它都会重新刷新为3秒。
所有的球类都会在1秒的时间里下落1格高度,而你也可以在1s时间里向左或者向右移动一格,或者不动。当车筐与球重合时,表示你接到了球,你可以在一个位置同时接到多个球。
一开始,你可以选择任意的位置,那么你怎么规划你的移动路线,能够使得接到的球总积分最高呢?
第一行有三个整数n(1<=n<=100),m(1<=m<=1000),
n表示可以接到的球以及人可以站立的横向长度,m表示扔出的球的总数。
接下来m行,每行四个整数vi(0<=vi<=1e5),xi(0<=xi<n), yi(0<yi<=1000),ti(0<ti<=1000),vi表示球的积分,
xi表示物品的横向坐标,yi表示物品的初始高度,ti表示物品开始掉落的时间。当接收到vi==0的球时,会使你困在原地3秒,如果此时已经处于被困住的状态,则时间会重置为3秒。
玩家最多可以采集到的金矿总矿产值,数据保证所有金矿都可以到达。
输入
10 3
3 5 3 3
0 3 2 1
1 0 10 6
输出
4
输入
10 1
0 3 2 1
输出
0