GHOJ 667 垃圾陷阱

题目描述

　　卡门——Farmer John极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D（2≤D≤100)英尺。

　　卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。假设卡门预先知道了每个垃圾扔下的时间t（0＜t≤1000），以及每个垃圾堆放的高度h（1≤h≤25）和吃进该垃圾能维持生命的时间f（1≤f≤30），要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。

输入格式

　　第一行为2个整数，D和G（1≤G≤100），G为被投入井的垃圾的数量。

　　第二到第G+1行，每行包括3个整数：T（0＜T≤1000），表示垃圾被投进井中的时间；F（1≤F≤30），表示该垃圾能维持卡门生命的时间；和H（1≤H≤25），该垃圾能垫高的高度。

输出格式

　　如果卡门可以爬出陷阱，输出一个整数表示最早什么时候可以爬出；否则输出卡门最长可以存活多长时间。

输入样例

20 4

5 4 9

9 3 2

12 6 10

13 1 1

输出样例

样例说明

　　卡门堆放她收到的第一个垃圾：height=9；

　　卡门吃掉她收到的第二个垃圾，使她的生命从10小时延伸到13小时；

　　卡门堆放第3个垃圾，height=19；

　　卡门堆放第4个垃圾，height=20。

题解

　　我们设$dp[i]$为堆到高度为$i$时，奶牛最长的存活时间，此时这就是一个背包模板。

　　我们在模板里多判断一次当前$dp[d]$有没有被更新，如果有，就直接输出当前是第几个垃圾即可。否则最后输出$dp[0]$即可。

#include <iostream>
#include <algorithm>
#include <cstring>

#define MAX_N 100
#define MAX_M 100

using namespace std;

int n, m;
struct Trash
{
    int t;
    int w, v;
    inline bool operator < (const Trash & x) const
    {
        return t < x.t;
    }
};
Trash a[MAX_N + 5];
int dp[MAX_M + 5];

int main()
{
    cin >> m >> n;
    for(register int i = 1; i <= n; ++i)
    {
        cin >> a[i].t >> a[i].v >> a[i].w;
    }
    sort(a + 1, a + n + 1);
    dp[0] = 10;
    for(register int i = 1; i <= n; ++i)
    {
        for(register int j = m + a[i].w - 1; j >= m && j >= a[i].w; --j)
        {
            if(dp[j - a[i].w] < a[i].t) continue;
            cout << a[i].t;
            return 0;
        }
        for(register int j = m - 1; j >= a[i].w; --j)
        {
            if(dp[j] >= a[i].t) dp[j] += a[i].v;
            if(dp[j - a[i].w] >= a[i].t) dp[j] = max(dp[j], dp[j - a[i].w]);
        }
        for(register int j = a[i].w - 1; j >= 0; --j)
        {
            if(dp[j] >= a[i].t) dp[j] += a[i].v;
        }
    }
    cout << dp[0];
    return 0;
}

参考程序