题解 P1156 【垃圾陷阱】

huiwang17 · 2019-08-28 20:58:37 · 题解

要考虑怎么区分一个状态是否可行【这里是初始化为1了】 毕竟这是一头神奇的奶牛，血量为0的时候也可以进行其他的操作。。 然后和一般的背包不同的是

一般的背包若当前钱数小于商品价值的时候可以直接continue

但是这里你不把垃圾堆起来你会获得体力值哦！

所以状态转移的时候，要考虑只能吃掉而不能堆放的情况。也就是j应该从0开始枚举。

#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define ll long long
const int MAXN = 2505;
const int INF = 10000000;

struct laji{
    int t;
    int f;
    int h;
};

bool operator < (laji l1, laji l2){
    return l1.t < l2.t || (l1.t == l2.t && l1.h > l2.h);
}

int D, G;
laji a[150];
int f[105][260];

int main(){
    cin >> D >> G;
    for(int i = 1; i <= G; i++)
        cin >> a[i].t >> a[i].f >> a[i].h;
    sort(a + 1, a + 1 + G);
    memset(f, -1, sizeof(f));
    f[0][0] = 10;
    for(int i = 1; i <= G; i++)
        for(int j = 0; j < 260; j++){ //这里一定需要是从0开始，否则会导致某些状态无法向后传递。
            int wait = a[i].t - a[i-1].t;
            if(f[i-1][j] >= wait)
                f[i][j] = max(f[i][j], f[i-1][j] - wait + a[i].f);
            if(j >= a[i].h && f[i-1][j-a[i].h] >= wait) //这里j大于当前高度才能转移
                f[i][j] = max(f[i][j], f[i-1][j-a[i].h] - wait);
            if(f[i][j] >= 0 && j >= D){
                cout << a[i].t << endl;
                return 0;
            }
        }
    int ans = 0;
    for(int i = 1; i <= G; i++)
        if(f[i][0] > 0)
            ans = max(ans, a[i].t + f[i][0]);
    cout << ans << endl;
}