首先应该看得出是一个背包吧
那dp数组的第一维肯定有前i个物品
那第二维放啥呢？血量？高度？时间？
时间是完全可以排除的，因为牛肯定是在辣鸡刚掉下的时候就使用它，而且对于subtask1"如果卡门可以爬出陷阱，输出一个整数表示最早什么时候可以爬出"，答案肯定刚好是某个辣鸡下落的时间
血量呢？设dp[i][j]代表前i件物品处理后能苟到j时间（其实相当于j血量）达到的最大高度
则有dp[i][j]=max(dp[i−1][j]+trash[i].h,dp[i−1][j+trash[i].c]) //前一种状态相当于垫脚，后一种是拿来续命
然而对于j的取值，题目中并没有明确的给出，并不好枚举，所以只有高度了
设dp[i][j]代表前i件物品处理后在j高度时能苟住的最长时间
则有 dp[i][j]=max(dp[i−1][j]+trash[i].c,dp[i−1][j−trash[i].h]) //前一种续命，后一种垫脚
j只需要从0~D枚举即可 注意在转移的时候 需要先判断上一个阶段到底能不能苟到这个垃圾掉下来的时候
#include<bits/stdc++.h> #define N 105 using namespace std; int D,G,dp[N][1005]; struct Node { int T,F,H; }trash[N]; inline bool cmp(const Node &a,const Node &b) { return a.T<b.T; } int main() { cin>>D>>G; for(int i=1;i<=G;i++) { cin>>trash[i].T>>trash[i].F>>trash[i].H; } sort(trash+1,trash+G+1,cmp); memset(dp,-1,sizeof(dp)); dp[0][0]=10; for(int i=1;i<=G;i++) { for(int j=0;j<=D;j++) { if(j>=trash[i].H&&dp[i-1][j-trash[i].H]>=trash[i].T) dp[i][j]=max(dp[i][j],dp[i-1][j-trash[i].H]); if(dp[i-1][j]>=trash[i].T) dp[i][j]=max(dp[i][j],dp[i-1][j]+trash[i].F); } } int max_height=0; int max_time=0; for(int i=1;i<=G;i++) { for(int j=0;j<=D;j++) { if(dp[i][j]>=trash[i].T) max_height=max(max_height,j); max_time=max(max_time,dp[i][j]); } if(max_height==D) { cout<<trash[i].T<<endl; return 0; } } cout<<max_time<<endl; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9827611.html
