USACO题解

这是一道经典的$USACO$动态规划题。

思路

把垃圾按时间$T$从小到大排序。设：

$dp[i][j]$：处理到第$i$个垃圾（按时间排序后），当前堆叠高度为$j$时，卡门剩余的最大存活时间（即"当前时刻 + 剩余能量"）。如果该状态不可达则为负无穷。
转移时对第 i 个垃圾（时间$t$，食物$f$，高度$h$）有两种选择：
1.
吃掉：高度不变，$dp[i][j] = hmax(dp[i][j], dp[i-1][j] + f)$
2.
堆起来： $dp[i][j] = max(dp[i][j], dp[i-1][j-h])$ （要求$j >= h$且$dp[i-1][j-h] >= t$，即在该垃圾落下时卡门还活着）
初始$dp[0][0] = 10$（初始 10 小时能量）。

由于$D ≤ 100$，高度这一维最多到$D$（超过$D$就算逃出去了，不需要再记录）。

答案判定：

在所有$dp[i][j] >= t_i$且$ j + h_i >= D$的状态中，取最小的 $t_i$ 作为逃出时间。如果无法逃出，则答案为所有可达状态 $dp[G][j]$ 的最大值（即最长存活时间）。

细节：

题目说"若体力值为 0 时吃下垃圾或逃出井外也不会饿死"，且"10 小时内（不含 10 小时）没有进食会饿死"。这意味着卡门在时刻$x$死亡当且仅当她的"死亡时间"（当前时间 + 剩余能量）严格小于 下一个要处理的垃圾落下时间。因此转移时要求$dp[i-1][j-h] >= t$（等于$t$时刚好能撑到垃圾落下，不算饿死）。

C++代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

struct Garbage {
    int t, f, h;
    bool operator<(const Garbage& other) const {
        return t < other.t;
    }
};

int main() {
    int D, G;
    cin >> D >> G;
    Garbage g[105];
    for (int i = 1; i <= G; i++) {
        cin >> g[i].t >> g[i].f >> g[i].h;
    }
    sort(g + 1, g + G + 1);

    // dp[j] = 当前堆叠高度为 j 时，卡门剩余的最大存活时间（当前时刻+能量）
    // 初始：时刻 0，高度 0，能量 10
    int dp[105];
    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 10;

    int escapeTime = -1;   // 最早逃出时间
    int maxSurvive = 10;   // 最长存活时间

    for (int i = 1; i <= G; i++) {
        int t = g[i].t, f = g[i].f, h = g[i].h;
        // 从大到小更新高度，避免同一垃圾被重复堆放
        for (int j = D; j >= 0; j--) {
            if (dp[j] < 0) continue;
            // 检查在垃圾 i 落下时是否还活着：dp[j] 表示"当前时刻+剩余能量"
            // 由于 dp[j] 是在处理第 i-1 个垃圾时更新的，其对应的"当前时刻"是 g[i-1].t
            // 所以需要 dp[j] >= t 才能活到垃圾 i 落下
            if (dp[j] < t) continue;

            // 选择 1：吃掉
            dp[j] = dp[j] + f;

            // 选择 2：堆放（需要 j + h >= 0，即原高度 j-h >= 0）
            if (j + h >= D) {
                // 可以逃出，更新最早逃出时间
                if (escapeTime == -1 || t < escapeTime) {
                    escapeTime = t;
                }
            } else {
                dp[j + h] = max(dp[j + h], dp[j]);
            }
        }
    }

    if (escapeTime != -1) {
        cout << escapeTime << endl;
    } else {
        // 无法逃出，求最长存活时间
        int ans = 0;
        for (int j = 0; j <= D; j++) {
            ans = max(ans, dp[j]);
        }
        cout << ans << endl;
    }
    return 0;
}

注意：上面代码在"堆放"转移时有个细节——当$j + h >= D$时直接判断逃出，不再更新$dp$。这等价于把高度上限设为$D$，因为超过$D$的状态对后续无意义（已经逃出了）。另外，由于一维滚动数组从大到小遍历，同一垃圾不会被重复用于堆放。