卡门想把垃圾堆起来,等到堆得与井同样高时,她就能逃出井外了。另外,卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放,并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间t (0 < t \le 1000),以及每个垃圾堆放的高度h(1 \le h \le 25)和吃进该垃圾能维持生命的时间f(1 \le f \le 30),要求出卡门最早能逃出井外的时间,假设卡门当前体内有足够持续10小时的能量,如果卡门10小时内没有进食,卡门就将饿死。

吃下该物品,则血量增加 w_i

堆放该物品,血量减 1,高度增加 h_i

物品还带有时间维,所以我们可以预先对所有物品进行排序,保证物品这维增长是线性的。

转移比较难思考,第一种转移是从 f_{i-1j} 来的,而第二种转移是要到 f_{ij+h_i} 去,所以写的方式还有些不同。

转移方程:

表示堆放该物品的转移。

在这里,我们并不需要倒序循环 j (因为第一维循环保证用i-1阶段更新i),但是如果需要用滚动数组优化的话,为了避免重复更新需要倒序循环。

并且在转移过程中,如果当前血量足够下一次跳就可以跳出陷阱,就可以直接终止循环,记录答案了。因为从小到大枚举 i 所以可以保证答案最优。

最后,如果实在填不满的话,从头开始模拟一遍即可。