题解 P1156 【垃圾陷阱】
根据这道题的无后效性 ，以及题目的标签显然是道dp的题目。那么就应该看出是一个背包问题吧。
一维背包的模板+优化：
for(int i=1; i<=m; i++) { // weight
for(int j=n; j>=w[i]; j--) { // things;
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}把垃圾的高度看成物重（weight），能增加的生命的长短看成价值（things）。（不然不好做，写的时候多尝试）
然后把井的深度看成包的大小（n），垃圾的个数为物品数量（m）。（与上一一对应，但还需改动）
要求必须把包填满，所能取得的最小价值。
用一个结构体定义垃圾的 t（表示垃圾被投进井中的时间）,f（表示该垃圾能维持卡门生命的时间）,h（该垃圾能垫高的高度）。
struct per {
int t;
int f;
int h;
} r[105];//rubish-然后以时间排序（由题意，显然）
bool cmp(per a,per b) {
return a.t<b.t;
}
与
sort(r+1,r+g+1,cmp); 以上都是预备工作。
focus on ！！！！！
核心的状态转移方程 ：
-
dp[height+r[j].h]=max(dp[height+r[j].h],dp[height]);//不吃，叠高度，将第j个垃圾的高度从高度height叠上去，然后，与叠上去的高度 height+r[j].h，取最大的生命值。
-
dp[height]+=r[j].f;//不吃，直接在原高度加生命值
别忘了，要加上判断
if(dp[height]>=r[j].t) //在这个时间，牛牛还没gg（之前已经用时间排过序了，时间递增）
来个完整的code：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int d,g,k=1,ans;
struct per {
int t;
int f;
int h;
} r[105];
int dp[2505];
bool cmp(per a,per b) {
return a.t<b.t;
}
int main() {
cin>>d>>g;
for(int j=1; j<=g; j++)
cin>>r[j].t>>r[j].f>>r[j].h;
sort(r+1,r+g+1,cmp);
————————————————————————
ans=10;//这一段是为了判断最大活了多久，可以与下面和在一起，但循环展开更快（手动滑稽）。
for(int j=1; j<=g; j++)
if(ans>=r[j].t) ans+=r[j].f;//很显然的算法
————————————————————————
dp[0]=10；//刚开始的初始化
for(int j=1; j<=g; j++)
for(int height=d-r[j].h; height>=0; height--) //记得倒过来，他会反着刷过来，实在不会换2维数组也可以
if(dp[height]>=r[j].t) {
dp[height+r[j].h]=max(dp[height+r[j].h],dp[height]);
if(dp[d]>0) {//最大高度的生命值不为0了，就说明，牛牛已经到了井的顶端
printf("%d ",r[j].t);
return 0;
}
dp[height]+=r[j].f;
}
printf("%d",ans);//到不了，输出活最久的时间
return 0;
}
don't copy please
个人感觉简单易懂 ，还很短，希望有帮助。
φ(>ω<) 求过加点顶 (>ω･ )ﾉ