题解 P1156 【垃圾陷阱】

先将每一个垃圾按出现时间升序排序

定义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

这样就可以了

实验证明,其实可以不用判断是否有负数高度或血量的情况(不知是不是数据水?)

同时发表:http://blog.csdn.net/Nidhogg\_\_/article/details/70445104

#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);
    }
}

发表于 2017-04-25 16:25:01 in 题解