P1156

RoRoyyy · 2019-10-25 15:07:25 · 题解

状态和方程注释写的很清楚。

这里强调几个坑点！！

1.

牛这一把血量为0时但是还没死， 可以吃垃圾回血， 不会死。

2.

牛在操作垃圾的时候必须保证自己不死。

3.

当牛操作完垃圾之后如果能使高度大于h且自己不死那么就结束了， 直接输出此时用时是多少。也就是如果能有状态转移到dp[i][h]那么就成功了， 为了简便， 一开始把所有状态初始化为-inf

4.

牛在出来的最后一刻可以血量为0....也就是出来的时候正好死是可以的。

//RoRoyyy

/*
    dp[i][j] 表示第i个垃圾， 高度为j的最大血量
    1.把垃圾吃了    dp[i][j] max= dp[i - 1][j] + eat[i] - (t[i] - t[i - 1])
    2.放垃圾        dp[i][j] max= dp[i - 1][j - h[i]] - (t[i] - t[i - 1])
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 105;
int n, m;
struct node {
    int t, eat, hei;
    friend bool operator < (node a, node b) {
        return a.t < b.t;
    }
}rub[N];
int dp[N * 10][N];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) 
        scanf("%d%d%d", &rub[i].t, &rub[i].eat, &rub[i].hei);
    sort(rub + 1, rub + 1 + m);
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 10;
    for(int i = 1; i <= m; i++) {
        for(int j = 0; j <= n; j++) {
            if(dp[i - 1][j] - (rub[i].t - rub[i - 1].t) >= 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + rub[i].eat - (rub[i].t - rub[i - 1].t));
            if(j - rub[i].hei >= 0 && dp[i - 1][j - rub[i].hei] - (rub[i].t - rub[i - 1].t) >= 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - rub[i].hei] - (rub[i].t - rub[i - 1].t));
        }
        if(dp[i][n] >= 0) {
            printf("%d\n", rub[i].t);
            return 0;
        }
    }
    int ans = -0x3f3f3f3f;
    for(int i = 0; i <= m; i++) ans = max(ans, dp[i][0] + rub[i].t);
    printf("%d\n", ans);
    return 0;
}