[洛谷P1156]垃圾陷阱lyh's blog

难度：提高+/省选-

题目描述

        卡门――农夫约翰极其珍视的一条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)，该垃圾能垫高的高度。

输出格式:

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

输入输出样例

Sample input

20 4
5 4 9
9 3 2
12 6 10
13 1 1

Sample output

13

题解

题目考察动态规划。这里提供三种解决思路。
要先对垃圾投入时间升序排列，确定序号。

三维DP法:
        分析题目，状态量有垃圾序号，生命值，高度和绝对时间四种。一种解决思路是将垃圾序号，生命值和高度作为状态描述参量，对绝对时间求DP。
        若令dp(r，l，h)表示在处理到第r个垃圾，生命值为l，高度为h时的最优逃出时间，则状态转移方程为:
        time(r+1)>l时:

$dp(r，l，h)=inf$

h+height(r)<d时:

$dp(r，l，h)=\min\{dp(r+1，l+life(r)，h)，dp(r+1，l，h+height(r))\}$

否则:

$dp(r，l，h)=time(r)$

起初，dp所有元素均置为0。inf表示无穷大。考虑到数据量大小，可以递归而非递推求解，但缺点是空间消耗过大，状态参量过多。
答案即为dp(1，10，0)，若其为inf，说明无法逃出。在递归过程中用一个变量记录最长生存期，最后输出这个值即可。

#include<iostream>
#include<algorithm>

#define inf (int)1e9
using namespace std;
int dp[3200][101][101] = {0};
int d, g;

struct node {
    int t, v, h;

    bool operator<(node x) {
        if (this->t < x.t)return true;
        return false;
    }
} op[101];

int maxh = 0;

int DP(int l, int r, int h) {
    if (dp[l][r][h] != 0)return dp[l][r][h];
    if (op[r].t > l || r == g + 1) {
        maxh = max(maxh, l);
        return dp[l][r][h] = inf;
    }
    if (h + op[r].h >= d)return dp[l][r][h] = op[r].t;
    return dp[l][r][h] = min(DP(l + op[r].v, r + 1, h), DP(l, r + 1, h + op[r].h));
}

int main() {
    cin >> d >> g;
    for (int i = 1; i <= g; i++)cin >> op[i].t >> op[i].v >> op[i].h;
    sort(op + 1, op + g + 1);
    if (DP(10, 1, 0) < inf)cout << DP(10, 1, 0);
    else cout << maxh;
    return 0;
}

二维DP法:
        只考虑垃圾序号和高度两个参量，对生命值求dp。
        令dp(r，h)表示处理了前r个垃圾，高度达到h时的最大生存期。状态转移方程为:
        time(r+1)≤dp(r，h)时:

$dp(r+1，h)=\max\{dp(r，h)+life(r+1)，dp(r，h-height(r+1))\}$

        起初所有dp元素全置为-1并初始化dp[0][0]=10，按照上述方程递推。结合方程特点，递推应按照从左到右，从上到下的顺序。行坐标范围为[0，G)，列坐标范围[0，D)。当其中出现dp(i，j)不为-1且j>=d的情况时，记录逃出时间为time(i)。
        最后遍历一遍二维表获得最大的dp(i，j)，此为最大生存期，注意行坐标范围为[0，G]。
        时间复杂度O(D×G)。

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

#define inf (int)1e9
using namespace std;
int dp[3200][150];
int d, g;

struct node {
    int t, v, h;

    bool operator<(node x) {
        if (this->t < x.t)return true;
        return false;
    }
} op[101];

int maxt = 0;
int mint = inf;

int main() {
    cin >> d >> g;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= g; i++)cin >> op[i].t >> op[i].v >> op[i].h;
    sort(op + 1, op + g + 1);
    dp[0][0] = 10;
    for (int i = 0; i < g; i++) {
        for (int j = 0; j <= d; j++) {
            if (op[i + 1].t <= dp[i][j]) {
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + op[i + 1].v);
                if (j + op[i + 1].h >= d)mint = min(mint, op[i + 1].t);
                dp[i + 1][j + op[i + 1].h] = max(dp[i + 1][j + op[i + 1].h], dp[i][j]);
            }
        }
    }
    for (int i = 0; i <= g; i++)
        for (int j = 0; j < d; j++)maxt = max(maxt, dp[i][j]);
    if (mint != inf)cout << mint;
    else cout << maxt;
    return 0;
}

善于发现的读者可能会注意到，这个二维DP只与两个相邻的行有关，容易发现dp数组可以压缩至一维。考虑到每一个元素只可能影响它正下方和正下方右边的某一值，我们应采取从上到下，从右到左的顺序进行DP。除此之外还要注意值修改顺序的不同。这便是解决本题的第三个方法，也是最优的方法。

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

#define inf (int)1e9
using namespace std;
int dp[200];
int d, g;

struct node {
    int t, v, h;

    bool operator<(node x) {
        if (this->t < x.t)return true;
        return false;
    }
} op[101];

int maxt = 0;
int mint = inf;

int main() {
    cin >> d >> g;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= g; i++)cin >> op[i].t >> op[i].v >> op[i].h;
    sort(op + 1, op + g + 1);
    dp[0] = 10;
    for (int i = 0; i < g; i++) {
        for (int j = d - 1; j >= 0; j--) {
            if (op[i + 1].t <= dp[j]) {
                if (j + op[i + 1].h >= d)mint = min(mint, op[i + 1].t);
                dp[j + op[i + 1].h] = max(dp[j + op[i + 1].h], dp[j]);
                maxt = max(maxt, dp[j]);
                dp[j] = max(dp[j], dp[j] + op[i + 1].v);
                maxt = max(maxt, dp[j]);
            }
        }
    }
    if (mint != inf)cout << mint;
    else cout << maxt;
    return 0;
}

        这里总结一下动态规划问题的求解模型。
        1. 确定状态和状态之间的关系，理清那些是状态的描述量，那些是所求量。
        2. 列出状态转移方程。
        3. 观察状态转移方程，确定递推顺序。
        4#. 必要时应采取状态压缩DP，离散化(后文详述)和数组维数压缩的方法降低空间复杂度。
        DP降维的方法有以下几种:
        1. 状态之间可以互相表示，这时可以去除一些状态。
        2. 该状态没有必要或者不影响递推过程。
        由上文的讲述，可以发现选取正确的状态参量来描述状态是一件很有意义的事情。选取状态时不仅要紧抓题目要点，还要尽可能精简。状态参量过少会难以描述状态甚至无法转移，过多很容易造成时间和空间的浪费。这一种能力既需要深厚的经验积累，有时又需要一点点灵感和大胆的猜想。