题意

卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

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

假设卡门预先知道了每个垃圾扔下的时间t，以及每个垃圾堆放的高度h和吃进该垃圾能维持生命的时间f，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。

分析

每个垃圾都有两种可能，有点类似01背包。

考虑到在高度一定的情况下，存活时间越长就越有可能成功（因为可能可以获得更多垃圾）。设 \(f[i][j]\) 为前 \(i\)​ 个垃圾，当前高度为 \(j\) 的最大存活时间。

每个状态可以由其上个物品增加高度或将上个物品吃掉得来。列出状态转移方程

\[f[i][j]=max(f[i-1][j-h[i]],f[i-1][j]+t[i]) \]

实现的时候可以用“我到哪里去”的转移方法实现。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int maxm = 1100;
int f[maxm], d, g;
struct node
{
    int t, f, h;
    bool operator< (const node a) const
    {
        return t < a.t;
    }
} a[maxn];
int main()
{
    cin >> d >> g;
    for (int i = 1; i <= g; i++)
        cin >> a[i].t >> a[i].f >> a[i].h;
    sort(a + 1, a + 1 + g);
    f[0] = 10;
    for (int i = 1; i <= g; i++)
        for (int j = d; j >= 0; j--)
        {
            if (a[i].t > f[j]) //如果当前存活时间还拿不了当前物品
                continue;
            if (j + a[i].h >= d) //如果已经可以出去了
            {
                cout << a[i].t << endl;
                return 0;
            }
            f[j + a[i].h] = max(f[j + a[i].h], f[j]); //增加高度的转移
            f[j] += a[i].f; // 吃掉的转移
        }
    cout << f[0] << endl; // 如果出不去，输出高度为 0 时存活时间（即全部拿来吃）
    return 0;
}