题目描述

卡门——农夫约翰极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D (2 <= D <= 100)英尺。
卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间t(0

思路

先将每一个垃圾按出现时间升序排序
定义a.x为出现时间a.h为高度a.t为吃下获得的血量
f[i][j]表示前i个垃圾在到达j的高度时剩余的最大血量
显而易见开始时f[0][0]为10
枚举一个i为垃圾编号j为高度,就有:
1.吃下这个垃圾f[i][j]=max{f[i][j],f[i-1][j]-(a[i].x-a[i-1].x)+a[i].t}
初始f[i][j]为-INF,a[i].x-a[i-1].x为从上一个垃圾到这一个垃圾要经过多少时间
而且显然要当f[i-1][j]-(a[i].x-a[i-1].x)>=0时才在当前时间是存活着的才可以吃下这个垃圾,吃下这个垃圾回复的血量就是a[i].t,且这只牛很厉害可以在刚好死的时候吃下一个垃圾(+1s)
2.将这个垃圾叠起来f[i][j]=max{f[i][j],f[i-1][j-a[i].h]-a[i].x+a[i-1].x}
在这种情况中显然我们如果可以将当前垃圾放置并达到j这个高度时在当前高度减去当前垃圾的高度a[i].h,即([j-a[i].h)要有一个可以在经过(a[i].x-a[i-1].x)的时间仍然存活，当然j-a[i].h要>=0,时间为负数显然是不可能的
而且这只牛很厉害,在生命的最后一秒仍然可以堆上一个垃圾(+1s)
这时如过我们枚举的高度j达到了目标高度n(要满足血量>=0)我们就可以直接输出a[i].x
为什么呢，因为开始时我们排了一次序，且我们是以每一个垃圾为外循环进行枚举的，所以当有一个j达到了目标高度那么肯定是最优的
当我们出了最优解后就可以直接退出了
但如果没有找到最优解，那我们就重新枚举一次此时的答案ans为max{ans,f[i][j]+a[i].x}
因为在到达了的i个垃圾后我们还可以再撑f[i][j]s
这样就可以了
实验证明，其实可以不用判断是否有负数高度或血量的情况(不知是不是数据水?)

#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxn 1001
#define INF 0x7f7f7f7f
#define max(x,y) x>y?x:y
int f[101][1001];
struct arr
{
    int x,t,h;
}a[maxn];
int cmp(arr a,arr b)
{
    return a.x<b.x;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].t,&a[i].h);
    }
    sort(a+1,a+m+1,cmp);
    for (int i=0;i<=m;i++)
        for (int j=0;j<=n;j++)
            f[i][j]=-INF;
    f[0][0]=10; a[0].x=a[0].t=a[0].h=0;
    int fl=0;
    for (int i=1;i<=m;i++)
    {
        for (int j=0;j<=n;j++)
        {

            if (f[i-1][j]-a[i].x+a[i-1].x>=0) 
            {
                f[i][j]=max(f[i][j],f[i-1][j]-a[i].x+a[i-1].x+a[i].t);
            }
            if (f[i-1][j-a[i].h]-a[i].x+a[i-1].x>=0&&j-a[i].h>=0) 
            {
                f[i][j]=max(f[i][j],f[i-1][j-a[i].h]-a[i].x+a[i-1].x);
                if (j==n)
                {
                    printf("%d\n",a[i].x);
                    fl=1;
                    return 0;
                }
            }
        }
    }
    int ans=0;
    if (!fl)
    {
        for (int i=0;i<=m;i++)
            for (int j=0;j<=n;j++)
                if (f[i][j]!=INF)
                ans=max(ans,f[i][j]+a[i].x);
        printf("%d\n",ans);
    }
}