洛谷 1156 dp

#洛谷1156 dp 类背包问题

老久没有自己想出来过dp方程了，，，虽然到最后还是只写了30分，，，

设dp[j]表示最大生命值为i时的最大高度，则对于每个物品，可以选择吃掉或者放上去，即转移为dp[j + p[i].eatLife] 或 dp[j] + p[i].putHeight

注意转移顺序

做这道题目的时候WA了一个世纪，死活找不出原因，最后在codevs上扣下来数据才终于Get到

1.注意dp的初值设定，开始时没注意用的0，后来才发现需要搞成-inf，只把dp[10]设为0

2.注意最大生存时间的计算，开始脑抽的认为吃掉所有垃圾，后来看到数据才意识到有些垃圾可能在扔下来之前就死了，需要判定



#include <cstdio>

#include <cstring>

#include <algorithm>

struct data {

    int putTime;

    int eatLife;

    int putHeight;

};

const int inf = 0x3f3f3f3f;

const int maxn = 100 + 10;

data p[maxn];

int d, n;

int dp[2000];

int totTime;

bool cmp(data aa, data bb) {

    return aa.putTime < bb.putTime;

}

int main () {

    scanf("%d %d", &d, &n);

    for (int i = 1; i <= n; i++) scanf("%d %d %d", &p[i].putTime, &p[i].eatLife, &p[i].putHeight);

    memset(dp, 192, sizeof(dp));

    dp[10] = 0;

    std :: sort(&p[1], &p[n+1], cmp);

    for (int i = 1; i <= n; i++) {

        for (int j = p[n].putTime; j >= p[i].putTime; j--) {

            dp[j + p[i].eatLife] = std :: max(dp[j + p[i].eatLife], dp[j]);

            dp[j] += p[i].putHeight;

        }

    }

    for (int i = 10; i <= p[n].putTime; i++) {

        if (dp[i] >= d) {

            printf("%d", i);

            return 0;

        }

    }

    int j = 10;

    for (int i = 1; i <= n && j >= p[i].putTime; i++) {

        j += p[i].eatLife;

    }

    printf("%d", j);

    return 0;

}

巴特西

洛谷 1156 dp

最新文章

热门文章