P1156 垃圾陷阱

每个垃圾只能用一次，典型的01背包。
关键是时间的处理
ll f[N];题目要中求的是生存的最长时间，所以这里的f[i]是指高度i时生存的最长时间
对于每一块垃圾，我们都有两种选择，吃，或者不吃。这里时间的处理类似迷宫DP，对于i，求所有能到达这一高度的时间中取最大值，不用记录时间段，每次加上高度试探一下，如果可以直接逃出去就输出这一块垃圾到来的时间即可。因为数据中没说是否按照T升序，所以最好先自己排个序。
然后转移方程：
不吃：

f[j+e[i].H]=max(f[j],f[j+e[i].H]);//不吃，直接摞上去，比较所有能到达这里的时间（有点像那个迷宫DP）

吃就直接吃
f[j]=f[j]+e[i].F;

还有以后我都要用这种方式写for 循环

#define over(i,s,t) for(int i=s;i<=t;++i)//这一手直接解决困扰我多年的for函数+-打错的问题！！

不是为了方便和装逼，是为了减少我***手残的bug，已经好多次，debug一个小时发现是++写成--了…

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(int i=s;i<=t;++i)//这一手直接解决困扰我多年的for函数+-打错的问题！！
#define lver(i,t,s) for(int i=t;i>=s;--i)
using namespace std;
typedef long long ll;
const ll N=1e6+7;
const ll mod=2147483647;
const double EPS=1e-6;
ll f[N];//题目要中求的是生存的最长时间，所以这里的f[i]是指高度i时生存的最长时间
struct node
{
    ll T,F,H;
    bool operator<(const node &t)const
    {
        return T<t.T;
    }
}e[N];
ll n,D;
int main()
{
    scanf("%lld%lld",&D,&n);
    over(i,1,n)
        scanf("%lld%lld%lld",&e[i].T,&e[i].F,&e[i].H);
    sort(e+1,e+1+n);
    memset(f,-1,sizeof f);
    f[0]=10;
    over(i,1,n) lver(j,D,0)
    {
        if(f[j]>=e[i].T)//能活到这个时候
        {
            if(j+e[i].H>=D){
                printf("%lld\n",e[i].T);
                return 0;
            }
            f[j+e[i].H]=max(f[j],f[j+e[i].H]);//不吃，直接摞上去，比较所有能到达这里的时间（有点像那个迷宫DP）
            f[j]=f[j]+e[i].F;
        }
    }
    printf("%lld\n",f[0]);
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜