[USACO01OPEN] 垃圾陷阱

题意

卡门掉进了垃圾井里，井深为 D。

一共有 G 个垃圾，第 i 个垃圾在时间 t_i 扔下，吃掉后可以增加 f_i 小时生命，堆起来可以增加 h_i 的高度。

卡门初始有 10 小时生命。她必须在垃圾到达时活着，才能选择把它吃掉或堆起来。

如果垃圾堆的总高度达到或超过 D，她就可以立刻逃出去。

要求输出最早的逃出时间；如果逃不出去，就输出她最长能活多久。

这张表把题意翻成了 DP 模型：

原题对象	DP 含义
当前高度	状态
当前还能活到的最晚时间	状态值
吃掉一个垃圾	生命时间增加
堆起一个垃圾	高度增加

思路

一句话本质：按垃圾掉落时间排序后，在每个高度上维护"最晚还能活到什么时候"。每个垃圾选吃（延命）或堆（加高），一旦高度到达 $D$ 即逃出。

先看最直接的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38import sys

data = list(map(int, sys.stdin.buffer.read().split()))
D, G = data[0], data[1]
garbages = []
idx = 2
for _ in range(G):
    t, f, h = data[idx], data[idx + 1], data[idx + 2]
    idx += 3
    garbages.append((t, f, h))

garbages.sort()

best_escape = 10**9
max_life = 10

def dfs(i, health, height, cur_time):
    global best_escape, max_life
    if height >= D:
        best_escape = min(best_escape, cur_time)
        return
    if i == G:
        max_life = max(max_life, health)
        return
    t, f, h = garbages[i]
    if health < t:
        max_life = max(max_life, health)
        return
    dead_line = health
    dfs(i + 1, health + f, height, t)
    dfs(i + 1, health, height + h, t)

dfs(0, 10, 0, 0)

if best_escape != 10**9:
    print(best_escape)
else:
    print(max_life)

brute.py 对每个垃圾递归分叉"吃"或"堆"， $G$ 最大 $100$ ， $2^{100}$ 完全不可行。

为什么必须先排序？

垃圾在不同时间落下，先掉落的垃圾必须先处理——你不可能在时间 $3$ 时吃掉时间 $5$ 才会掉的垃圾。排序后，处理顺序和物理时间一致，可以按时间 $t_i$ 依次决策。

排序后，每个垃圾只有两个选择，怎么设计状态？

当前的状态由"堆了多高"和"还能活到什么时候"决定。设 $dp_h$ 表示在当前已处理过的垃圾中，堆到高度 $h$ 时卡门最晚能活到的绝对时间。

为什么存"绝对时间"而不是"剩余生命"？

垃圾掉落时间是绝对时间 $t_i$ ，判断能不能处理要看"当前生命 $\geqslant t_i$ "。用绝对时间直接比较，比"剩余生命 + 已过时间"更清晰。

吃和堆分别怎么转移？

吃：高度不变，生命 $+ f_i$ → $dp_h \leftarrow \max(dp_h,\ old_h + f_i)$
堆：生命不变，高度 $+ h_i$ → $dp_{\min(D,\ h+h_i)} \leftarrow \max(dp_{\min(D,\ h+h_i)},\ old_h)$

其中 $old_h$ 是处理当前垃圾前状态备份的值。高度超过 $D$ 时截断到 $D$ （已经能逃出，再高没有区别）。

什么时候宣告逃出？

一旦 $h + h_i \geqslant D$ 且 $old_h \geqslant t_i$ （堆的时候还活着），垃圾掉落时间 $t_i$ 就是最早逃出时间。如果处理完所有垃圾仍未逃出，答案就是 $\max_{0 \leqslant h \leqslant D} dp_h$ ，即最长存活时间。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#include <bits/stdc++.h>
using namespace std;

struct Garbage {
    int t, f, h;
    bool operator<(const Garbage& o) const {
        return t < o.t;                  // 按掉落时间升序
    }
};

const int MAXD = 105;

int D, G;
vector<Garbage> gb;
// dp[h] 表示当前堆叠高度为 h 时，奶牛的最大生命值。
int dp[MAXD];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> D >> G;
    gb.resize(G);
    for (int i = 0; i < G; i++) {
        cin >> gb[i].t >> gb[i].f >> gb[i].h;
    }
    sort(gb.begin(), gb.end());

    fill(dp, dp + D + 1, -1);
    dp[0] = 10;                           // 初始生命为 10

    for (int i = 0; i < G; i++) {
        int t = gb[i].t, f = gb[i].f, h = gb[i].h;
        vector<int> ndp(dp, dp + D + 1);  // 旧状态备份
        for (int j = 0; j <= D; j++) {
            if (dp[j] < t) continue;     // 活不到这个垃圾落下的时刻
            int newh = j + h;
            if (newh >= D) {             // 堆叠高度足够，逃出
                cout << t << '\n';
                return 0;
            }
            ndp[newh] = max(ndp[newh], dp[j]);       // 堆放：高度增加，生命不变
            ndp[j] = max(ndp[j], dp[j] + f);          // 吃掉：高度不变，生命增加
        }
        memcpy(dp, ndp.data(), (D + 1) * sizeof(int));
    }

    int ans = 10;
    for (int j = 0; j <= D; j++) {
        if (dp[j] >= 0) {
            ans = max(ans, dp[j]);
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(G * D)$
空间复杂度： $O(D)$

这里 G <= 100、D <= 100，所以复杂度非常小。

总结

这题的核心不是“能不能活”，而是“在每个高度上，最晚能活到什么时候”。

把垃圾按时间排序后，每个垃圾只有“吃”和“堆”两种决策，直接做高度 DP 就能得到最早逃出时间或最长存活时间。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[USACO01OPEN] 垃圾陷阱

目录

题意

思路

代码

复杂度

总结

一图流解析