[USACO01OPEN] 垃圾陷阱

题意

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

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

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

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

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

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

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

思路

先看一个可以直接验证正确性的朴素解：

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
57
58
59#include <bits/stdc++.h>
using namespace std;

struct Item {
    int t;
    int f;
    int h;
};

static int D, G;
static vector<Item> a;
static int best_escape = INT_MAX;
static int best_survive = 0;

static void dfs(int idx, int height, int death_time) {
    if (height >= D) {
        best_escape = min(best_escape, a[idx - 1].t);
        return;
    }

    if (idx == G) {
        best_survive = max(best_survive, death_time);
        return;
    }

    const auto &it = a[idx];
    if (death_time < it.t) {
        best_survive = max(best_survive, death_time);
        return;
    }

    // 选择“吃”。
    dfs(idx + 1, height, death_time + it.f);

    // 选择“堆”。
    dfs(idx + 1, min(D, height + it.h), death_time);
}

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

    cin >> D >> G;
    a.resize(G);
    for (int i = 0; i < G; ++i) {
        cin >> a[i].t >> a[i].f >> a[i].h;
    }
    sort(a.begin(), a.end(), [](const Item &x, const Item &y) {
        return x.t < y.t;
    });

    dfs(0, 0, 10);
    if (best_escape != INT_MAX) {
        cout << best_escape << '\n';
    } else {
        cout << best_survive << '\n';
    }
    return 0;
}

brute.cpp 直接枚举每个垃圾是“吃”还是“堆”，适合小数据对拍。

关键观察是：

垃圾是按时间陆续出现的，所以必须先按 t_i 排序
只要知道“当前堆到多高”和“还能活到什么时候”，就能决定下一步

因此设 dp[h] 表示：处理完当前这些垃圾后，堆到高度 h 时，卡门最晚能活到的绝对时间。

这张表说明两个转移：

选择	高度变化	生命变化
吃掉	不变	`+ f_i`
堆起来	`+ h_i`	不变

因为垃圾个数只有 100，井深只有 100，所以高度状态直接开到 D 就够了。一旦某次堆放后高度达到 D，就说明已经逃出，当前垃圾的时间就是答案。

DP 公式

设 $dp_h$ 表示处理完当前这些垃圾后，堆到高度 $h$ 时卡门最晚能活到的绝对时间。初始化：

dp_0=10

只有当 $dp_h\geqslant t_i$ 时，才能处理第 $i$ 个垃圾。若处理前的值记为 $old_h$ ，吃掉它：

dp_h\leftarrow \max(dp_h,\ old_h+f_i)

堆起来：

dp_{\min(D,h+h_i)}\leftarrow \max(dp_{\min(D,h+h_i)},\ old_h)

第一次让高度达到 $D$ 的垃圾时间 $t_i$ 就是最早逃出时间。

公式解释：dp_h 存的是在高度 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#include <bits/stdc++.h>
using namespace std;

struct Item {
    int t;
    int f;
    int h;
};

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

    int D, G;
    cin >> D >> G;

    vector<Item> a(G);
    for (int i = 0; i < G; ++i) {
        cin >> a[i].t >> a[i].f >> a[i].h;
    }

    sort(a.begin(), a.end(), [](const Item &x, const Item &y) {
        return x.t < y.t;
    });

    vector<int> dp(D + 1, -1);
    dp[0] = 10;

    for (const auto &it : a) {
        vector<int> ndp = dp;
        for (int h = 0; h <= D; ++h) {
            if (dp[h] < it.t) {
                continue;
            }

            // 吃掉这个垃圾，生命时间增加。
            ndp[h] = max(ndp[h], dp[h] + it.f);

            // 把这个垃圾堆起来，高度增加。
            int nh = min(D, h + it.h);
            ndp[nh] = max(ndp[nh], dp[h]);
        }

        dp.swap(ndp);

        // 一旦高度达到 D，就可以立刻逃出。
        if (dp[D] >= it.t) {
            cout << it.t << '\n';
            return 0;
        }
    }

    cout << *max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}

复杂度

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

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

总结

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

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

一图流解析

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