luogu_1156: 垃圾陷阱

洛谷1156：垃圾陷阱

题目描述：

• 一头牛在一个井里，深度为\(D(1\leq D\leq100)\)
• 每过一段时间会往井里投掷一个物品，牛可以选择将其堆起来或者吃掉，吃掉可以增加生命值(生命值随时间慢慢减少)，堆起来就离出口更近一些。同时知道牛的初试生命值为\(10\)。
• 询问如果牛可以爬出井，输出一个整数表示最早什么时候能够爬出；否则输出这头牛最长可以存活多长时间。

输入格式：

• 第一行输入两个整数\(D\)和\(G\)表示深度和投入井的物品的数量。
• 加下来\(G\)行，每行输入\(3\)个整数:\(T(0<T\leq100)\)，表示物品被投入井中的时间；\(F(1\leq F\leq30)\)，表示物品能增加的生命值；\(H(1\leq H\leq25)\)，该物品能垫多少高度。

输出格式：

• 输出一个整数表示答案。

思路：

• 背包问题
• 把井的深度看成是背包的容积。
• 把堆的物品的高度看成是物品的体积，得到的生命值看成是物品的价值。
• 那么题目的要求就是在装满甚至装爆背包的前提下使价值最小。
• 首先将投入物品按照时间作为关键字排序。
• 那么对于牛来说，一件物品有吃掉它或者堆起来两种选择。
• 设\(f(i,j)\)表示在第\(i\)个物品时，高度为\(j\)的生命值最大值。
  • 初始状态下: \(f(0,0)=10\)，其他情况为\(-INF\)(其实这里我有点没搞懂，但是赋0就会wa掉，希望有人能评论区告诉我一下)
  • \(f(i,j)=max(f(i,j), f(i-1,j)+items(i).v-(items(i).t)-items(i-1).t))\)
  • \(f(i,j)=max(f(i,j),f(i-1,j-items(i).h)-(items(i).t-items(i-1).t))\)
• 那如果可以爬出来，这时候选一个时间最小值。
• 那如果不能爬出来，那么枚举一下\(f(i,j)\)的情况。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
int D, G, f[maxn][100+10], ans;
struct Node{
    int t, v, h;
}a[maxn];

bool cmp(Node a, Node b){
    return a.t < b.t;
}

int main()
{
    scanf("%d%d", &D, &G);
    for(int i = 1; i <= G; i++){
        auto &x = a[i];
        scanf("%d%d%d", &x.t, &x.v, &x.h);
    }
    sort(a + 1, a + 1 + G, cmp);
    for(int i = 0; i <= G; i++)
        for(int j = 0; j <= D; j++) f[i][j] = -INF;
    f[0][0] = 10;
    for(int i = 1; i <= G; i++)
        for(int j = 0; j <= D; j++)
        {
            if(f[i-1][j] >= a[i].t - a[i-1].t)
                f[i][j] = max(f[i][j], f[i-1][j]+a[i].v-(a[i].t-a[i-1].t));
            if(f[i-1][j-a[i].h] >= a[i].t-a[i-1].t && j >= a[i].h)
            {
                f[i][j] = max(f[i][j], f[i-1][j-a[i].h]-(a[i].t-a[i-1].t));
                if(j == D)
                {
                    printf("%d\n", a[i].t);
                    return 0;
                }
            }
        }
    ans = -1;
    for(int i = 1; i <= G; i++)
        for(int j = 0; j <= D; j++)
        ans = max(ans, f[i][j] + a[i].t);
    cout << ans << endl;
    return 0;
}

luogu_1156: 垃圾陷阱

原文：https://www.cnblogs.com/zxytxdy/p/11669305.html