【Luogu-P1156】垃圾陷阱

题意#

给定深井的深度 $D$ 和垃圾的数量 $G$.

XLL想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。

XLL可以通过吃垃圾来维持自己的生命。

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

给定每个垃圾扔下的时间 $t_i$，高度 $h_i$，可供维持 $f_i$ 小时的生命。

XLL在 $0$ 时刻位于井底，要保证任何时刻的生命储备时长（生命值） $>0$，初始时生命值为 $10$ 小时。

求最早何时爬出，或最长存活多久。

$2\leq D, G\leq 100$，$1\leq t\leq 1000$，$1\leq h\leq 25$，$1\leq f \leq 30$.

分析#

背包。

井 $\Rightarrow$ 背包大小，垃圾高度 $\Rightarrow$ 物品重量，维持生命的时长 $\Rightarrow$ 价值。

对物品按 $t_i$ 升序排序，顺序加入背包。

设 $g[i][j]$ 表示处理完前 $i$ 件物品后，高度为 $j$ 时的最大生命值，有转移：

$$g_{i, j} = \max\left\{\begin{array}{l}g_{i - 1, j} + f[i]\\g_{i-1, j-h[i]}\end{array}\right.$$

普通的 $0/1$ 背包即可解决。