题解 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

这样就可以了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x7fffffff
#define ll long long
#define one_by_one (karment[i].time-karment[i-1].time)
using namespace std;
ll sum,dep;
ll ans;
struct laji{ll time,food,high;}karment[10000]; 
ll dp[1005][1005];
bool cmp(laji a,laji b){return a.time<b.time;}
int main()
{
    ll i,j;
    //cout<<INF;
    cin>>dep>>sum;
    for(i=0;i<=sum;i++)
    for(j=0;j<=dep;j++)dp[i][j]=-INF;
    //cout<<dp[1][0];
    for(i=1;i<=sum;i++)cin>>karment[i].time>>karment[i].food>>karment[i].high;
    sort(karment+1,karment+sum+1,cmp);
    //for(i=1;i<=sum;i++)cout<<karment[i].time<<" ";
    dp[0][0]=10;
    karment[0].time=0;
    karment[0].high=0;
    karment[0].food=0;
    for(i=1;i<=sum;i++)
    for(j=0;j<=dep;j++)
    {
        //cout<<1;
        if(dp[i-1][j]-one_by_one>=0)
        dp[i][j]=max(dp[i][j],dp[i-1][j]-one_by_one+karment[i].food);
        if(dp[i-1][j-karment[i].high]-one_by_one>=0&&j-karment[i].high>=0)
        {
            dp[i][j]=max(dp[i][j],dp[i-1][j-karment[i].high]-one_by_one);
            //cout<<"nowlife: "<<dp[i][j]<<" "<<"high: "<<j<<" time: "<<karment[i].time<<endl;
            if(j==dep)
            {
                cout<<karment[i].time;
                return 0;
            }
        }
        //cout<<"nowlife: "<<dp[i][j]<<" "<<"high: "<<j<<" time: "<<karment[i].time<<endl;
    }
    //cout<<1<<endl;
    for(i=0;i<=sum;i++)
    for(j=0;j<=dep;j++)
    ans=max(ans,dp[i][j]+karment[i].time);
    cout<<ans;
    return 0;
}