Luogu P1156 垃圾陷阱

gate

很久以前就想做了，但是我太菜了不会qwq

这题的思路相当好啊！

因为垃圾掉下来是有时间顺序的，所以要先按时间排序

我刚开始写的是f[j]表示生命值为j时的最大高度。

不过因为生命值是随时间减少的，以时间作为一维，

下标必须要计算上一个垃圾的时间-当前垃圾的时间……总之状态转移会很麻烦x

根据贪心的思路…因为高度一定时，显然生命值越大越好，

不妨设f[j]为高度为j时的最大生命值。

这就转化为了一个背包问题：容量为深度的背包，每个垃圾的空间为能增加的高度，价值为能增加的hp。

那么就有：

堆：$f[j+a[i].w] = max(f[j+a[i].w], f[j])$

吃：$f[j] = max(f[j], f[j]+a[i].hp)$

$f[j]+a[i].hp$显然大于$f[j]$，第二句可以直接写为$f[j] += a[i].hp$

那么，这种转移可行的条件是当前生命值不小于这个垃圾的时间，即$f[j] >= a[i].t$

而跳出的条件是当前高度+这个垃圾的高度大于陷阱深度，直接返回这个垃圾的时间即可。

同时，在dp过程中，不断更新最大存活时间——其实也就是垃圾全部用来吃的hp，也就是f[0]的最大值。

 

代码如下w

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define MogeKo qwq
using namespace std;

const int maxn = 3005;
const int INF = 0x3f3f3f3f;
int m,n,mhp,f[maxn];

struct trash {
    int t,hp,w;
    bool operator < (const trash &N) const {
        return t < N.t;
    }
} a[maxn];

int main() {
    scanf("%d%d",&m,&n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d%d",&a[i].t,&a[i].hp,&a[i].w);
    sort(a+1,a+n+1);
    memset(f,-INF,sizeof(f));
    f[0] = 10;
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--) {
            if(f[j] < a[i].t) continue;
            if(j + a[i].w >= m) {
                printf("%d",a[i].t);
                return 0;
            }
            f[j+a[i].w] = max(f[j+a[i].w],f[j]);
            f[j] += a[i].hp;
            mhp = max(mhp,f[j]);
        }
    printf("%d",mhp);
    return 0;
}