垃圾陷阱

纯暴力搜索（28 分）

#include <bits/stdc++.h>
using namespace std;
// D 井的深度, G 垃圾数量
int D, G;
struct Trash
{
    // 落下的时间、能维持的生命、可以垫高的高度
    int t, f, h;
};
Trash a[105];
bool cmp(Trash a, Trash b)
{
    return a.t < b.t;
}
// 现在考虑第 now 个垃圾
// 之前高度为 H，能活到 F 点，达到 H/F 的时间是 T
int ans1, ans2; // 几点钟能出去、最多活到几点钟
void dfs(int now, int H, int F, int T)
{
    ans2 = max(ans2, F);
    if (H >= D)
        ans1 = min(ans1, T);
    if (now > G)
        return;
    // 判断能不能见到当前垃圾
    if (a[now].t > F)
        return;
    // 垫高
    dfs(now + 1, H + a[now].h, F, a[now].t);
    // 吃掉
    dfs(now + 1, H, F + a[now].f, a[now].t);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> D >> G;
    for (int i = 1; i <= G; i++)
        cin >> a[i].t >> a[i].f >> a[i].h;
    sort(a + 1, a + G + 1, cmp);
    if (G <= 20)
    {
        // 暴力搜索
        ans1 = 1001;
        ans2 = 0;
        dfs(1, 0, 10, 0);
        if (ans1 != 1001)
            cout << ans1;
        else
            cout << ans2;
        return 0;
    }
    return 0;
}

暴力搜索+假贪心（46 分）

#include <bits/stdc++.h>
using namespace std;
// D 井的深度, G 垃圾数量
int D, G;
struct Trash
{
    // 落下的时间、能维持的生命、可以垫高的高度
    int t, f, h;
};
Trash a[105];
bool cmp(Trash a, Trash b)
{
    return a.t < b.t;
}
// 现在考虑第 now 个垃圾
// 之前高度为 H，能活到 F 点，达到 H/F 的时间是 T
int ans1, ans2; // 几点钟能出去、最多活到几点钟
void dfs(int now, int H, int F, int T)
{
    ans2 = max(ans2, F);
    if (H >= D)
        ans1 = min(ans1, T);
    if (now > G)
        return;
    // 判断能不能见到当前垃圾
    if (a[now].t > F)
        return;
    // 垫高
    dfs(now + 1, H + a[now].h, F, a[now].t);
    // 吃掉
    dfs(now + 1, H, F + a[now].f, a[now].t);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> D >> G;
    for (int i = 1; i <= G; i++)
        cin >> a[i].t >> a[i].f >> a[i].h;
    sort(a + 1, a + G + 1, cmp);
    if (G <= 20)
    {
        // 暴力搜索
        ans1 = 1001;
        ans2 = 0;
        dfs(1, 0, 10, 0);
        if (ans1 != 1001)
            cout << ans1;
        else
            cout << ans2;
        return 0;
    }
    // 写一个假贪心，活不下来时，吃掉最近的垃圾
    int H, F, T; // 当前高度，当前能活到的时间，当前时间
    H = 0, F = 10;
    for (int i = 1; i <= G; i++)
    {
        // 吃垃圾直到能见到当前垃圾
        while (F < a[i].t)
        {
            // 吃一个垃圾
            int pos = -1;
            for (int j = i - 1; j >= 1; j--)
            {
                if (a[j].f == 0)
                    continue;
                if (pos == -1 ||
                    a[j].f < a[pos].f ||
                    a[j].f == a[pos].f && a[j].h < a[pos].h)
                    pos = j;
            }
            if (pos == -1)
                break;
            F += a[pos].f;
            H -= a[pos].h;
            a[pos].f = 0;
        }
        // 如果能见到，更新高度
        if (F >= a[i].t)
        {
            H += a[i].h;
            if (H >= D)
            {
                cout << a[i].t;
                return 0;
            }
        }
    }
    cout << F << "\n";
    return 0;
}

DP（100 分）

#include <bits/stdc++.h>
using namespace std;
// D 井的深度, G 垃圾数量
int D, G;
struct Trash
{
    // 落下的时间、能维持的生命、可以垫高的高度
    int t, f, h;
};
Trash a[105];
bool cmp(Trash a, Trash b)
{
    return a.t < b.t;
}
int f[105][1000 + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> D >> G;
    for (int i = 1; i <= G; i++)
        cin >> a[i].t >> a[i].f >> a[i].h;
    sort(a + 1, a + G + 1, cmp);
    memset(f, -1, sizeof(f));
    for (int i = 0; i <= 10; i++)
        f[0][i] = 0;
    for (int i = 0; i <= G - 1; i++)
    {
        for (int j = 0; j <= a[G].t; j++)
        {
            // 当前状态为前 i 个垃圾，生命为 j 时的状态
            if (f[i][j] == -1)
                continue;
            // 加入下一个垃圾时能否修改状态
            if (j < a[i + 1].t)
                f[i + 1][j] = f[i][j];
            else
            {
                // 下一个垃圾是吃了还是垫高
                // 垫高
                f[i + 1][j] = max(f[i + 1][j], f[i][j] + a[i + 1].h);
                // 吃了（吃完后的高度不变，生命可以达到 j~j+a[i+1].f）
                for (int k = j; k <= min(j + a[i + 1].f, a[G].t); k++)
                    f[i + 1][k] = max(f[i + 1][k], f[i][j]);
            }
        }
    }
    // 检查到第几个垃圾的时候能出去
    int pos = G + 1;
    for (int i = 0; i <= G; i++)
        for (int j = 0; j <= a[G].t; j++)
            if (f[i][j] >= D)
                pos = min(pos, i);
    if (pos != G + 1)
    {
        cout << a[pos].t;
        return 0;
    }
    // 单独计算能活多久
    int ans = 10;
    for (int i = 1; i <= G; i++)
        if (a[i].t <= ans)
            ans += a[i].f;
    cout << ans;
    return 0;
}