题面-P1156 垃圾陷阱
算法关键词：01DP
（边听边写）
看到这道题，第一反应是贪心，应该是CSP和NOIP做贪心做多了的原因。但是细看一下，发现不对，贪心不好做或不能做。所以根据“最大时间”以及吃或堆二选一，只有一次影响考虑使用DP，并且应该是01背包DP。
使用数组 \(dp_{i,j}\) 表示考虑前 \(i\) 个垃圾，当前堆积高度为 \(j\) 时可维持的最大生命值。想不下去，分析一下样例：
输入
20 4
5 4 9
9 3 2
12 6 10
13 1 1
输出
13
发现后一项和前一项有关联，优化为使用数组 \(dp_{i}\) 当前堆积高度为 \(i\) 时可维持的最大生命值。
初始状态也很简单，即开始时间为0，高度为0，最大生命为10。
开始考虑转移，如果我们要考虑一个垃圾，那么我们有几个需要考虑的。
生命值要足够
判断一下生命值够不够撑到这个垃圾掉下，很简单，判断一下即可。
如何处理此垃圾
显然可以选择堆放或者吃掉。
- 若选择堆放，则
\[dp_{j+h_i}=max(dp_{j+h_i},dp_j)
\]
- 若选择吃掉，则
\[dp_j=dp_j+f_i
\]
当然除以上两条外还要判断：如果高度足够，则直接输出当前逃脱的时间。
如果到最后还没有成功逃脱，则输出可以存货的最大时间。
最后总结一下步骤：
1.把垃圾根据掉落时间排序
2.初始化dp数组，dp[0]=10，其余为0
3.做dp（如上分析）
最后终于完成了这道题，可喜可贺！代码如下OvO
#include <bits/stdc++.h>
using namespace std;struct node{int t,f,h;
}a[110];
int dp[110];bool cmp(node x,node y){return x.t<y.t;
}int main (){int d,g;scanf("%d%d",&d,&g);for(int i=1;i<=g;i++){scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);}sort(a+1,a+g+1,cmp);//按时间排序垃圾 dp[0]=10;for(int i=1;i<=g;i++){for(int j=d;j>=0;j--){if(dp[j]>=a[i].t){if(j+a[i].h>=d){printf("%d",a[i].t);return 0;}//dp核心 dp[j+a[i].h]=max(dp[j+a[i].h],dp[j]);//选择堆放 dp[j]+=a[i].f;//选择吃掉垃圾 }}}printf("%d",dp[0]);return 0;
}