P1156 垃圾陷阱 背包dp

· · 题解

显然这道题可以转化成背包问题（把背包问题中的选或不选 转化为 是垫高高还是吃垃圾）

设dp[i][j]为用前i个垃圾堆成j高度的最大生命值

当吃这个食物垃圾的时候可以转移 dp[i-1][j] +rubbish[i].f -> dp[i][j]（当不会死的时候才能转移）

当垫高高的时候可以转移 dp[i-1][j-rubbish[i].h] -> dp[i][j] (当不会死且j-rubbish[i].h>=0的时候才能转移)

输出答案

预先处理一下最多能活多久。 在dp数组中扫一遍，找到最小的满足要求的答案，若不存在则输出最久生存时间。


/*
 * @Author: Dolphin_ 
 * @Date: 2019-08-14 16:29:23 
 * @Last Modified by: Dolphin_
 * @Last Modified time: 2019-08-14 16:48:30
 */
//f[i][j]表示用前i个垃圾 在j高度时能获得的最大生命值
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define _FOR(i, a, b) for (int i = a; i >= b; --i)
#define INF 0x7fffffff
inline void read(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int g,d,f[110][110];
struct node{
    int t,f,h;
}a[110000];
bool cmp(node a,node b)
{
    return a.t<b.t;
}
int main()
{
    //freopen("a.in","r",stdin);
    read(d);read(g);
    int sum=10;
    FOR(i,1,g)
    {
        read(a[i].t);read(a[i].f);read(a[i].h);
        //a[i].t是垃圾掉下来的时间   a[i].f是垃圾提供的血量   a[i].h是垃圾的高度
    }
    sort(a+1,a+1+g,cmp);
    FOR(i,1,g)
    {
        if(sum>=a[i].t)sum+=a[i].f;
        else break;
    }
    f[0][0]=10;
    FOR(i,1,g)
    {
        FOR(j,0,d)
        {
            //选这个吃
            if(f[i-1][j]>=a[i].t) f[i][j]=max(f[i][j],f[i-1][j]+a[i].f);
            //选这个垫高高
            if(j>=a[i].h&&f[i-1][j-a[i].h]>=a[i].t) f[i][j]=max(f[i][j],f[i-1][j-a[i].h]) ;
        }
    }
    int ans=INF;bool flag=true;
    FOR(i,1,g)
    {
        if(f[i][d]!=0)
        {
            ans=i;
            flag=false;
            break;
        }
    }
    if(flag)
    {
        printf("%d\n",sum);
    }else
    {
        printf("%d\n",a[ans].t);
    }
    return 0;
}