蒟蒻在DP之路上求索着

题目:传送门

问题描述

卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为$D(2 \le D \le 100)$英尺。

卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

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

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

数据范围

垃圾数$G\le 100$,每个垃圾被投放的时间$0<T\le 1000$,每个垃圾能维持卡门的生命时间$0<F\le 30$.每个垃圾能垫高的高度$0<H\le 25$.

题解

题目中有很多量,时间,生命值,高度,垃圾的个数.那么我们应该怎么设计状态呢?看到题目要求我们求时间,那么我们可以设$f[i][j]$表示一个有关i和j的状态所需的最小时间.但是我们发现剩下的状态有3个,而再加一维显然空间是撑不住的,那怎么办呢?我们必须想办法去掉一个变量.

我们发现,等待垃圾时的时间是不必要的,同时我们也没有必要把垃圾先留着,只需要在它被投放的时候选择怎么处理它.所以我们可以把时间这一维隐含在垃圾中,而没有必要对每个时间点做很多讨论和转移.现在我们有3个变量:垃圾,高度,生命值.对于每个垃圾,我们可以选择用来增加高度(不吃)或者增加生命值(吃),由这个讨论我们发现这是一个背包模型,因此我们选择前i个垃圾作为第一维,那么谁来做第二维呢?

看起来能不能出去和高度有更大的关系,所以我们可以尝试让生命值来做第二维,高度做数组的内容,这样高度足够时就判定有解.也就是设$f[i][j]$表示现在到了第i个垃圾,生命值为j时的最大高度.转移方程如下:
$$
f[i][j] = max(f[i-1][j]+h[i],f[i-1][j-hp[i]])
$$
最后进行答案的选择即可.写出来我们发现,生命值不仅会随着吃垃圾而增加,也会随着时间而减少,这时就对边界的判定产生了一些不便之处.那么我们试试用单调不下降的高度来作为第二维?
$$
f[i][j]=max(f[i-1][j-h[i]],f[i-1][j]+hp[i])
$$
我们发现这样也是对的,而且不必担心奇怪的边界问题.

代码:

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

int n, h, f[105][3500];

struct node
{
    int t, addhp, hight;
}r[105];

inline bool cmp(node x, node y)
{
    return x.t < y.t;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> h >> n;
    int tot = 0;
    for(int i = 1; i <= n; i++)
        cin >> r[i].t >> r[i].addhp >> r[i].hight, tot += r[i].addhp;
    sort(r + 1, r + 1 + n, cmp);
    memset(f, -64, sizeof(f));
    f[0][0] = 10, r[0].t = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = h; j >= 0; j--) {
            if (f[i - 1][j] < r[i].t - r[i - 1].t)continue;//不能从死亡状态转移过来
            if(j + r[i].hight >= h) {//如果出去了就直接输出这个垃圾被投放的时间
                cout << r[i].t << endl;
                return 0;
            }
            f[i][j+r[i].hight] = max(f[i][j+r[i].hight], f[i-1][j]-(r[i].t-r[i-1].t));
            f[i][j] = max(f[i - 1][j]+r[i].addhp-(r[i].t-r[i-1].t), f[i][j]);
        }
    }
    int maxlive = -100;
    for(int i = 1; i <= n; i++)
        maxlive = max(maxlive, f[i][0] + r[i].t);//取最长生命
    cout << maxlive << endl;
    return 0;
}