题目：https://www.luogu.org/problemnew/show/P1156
题意：
每一个垃圾投放时间是t，可以堆的高度是h，如果吃掉可以增加的生命值是f。
给定g个垃圾，初始生命值是10，要求如果要爬出深度为d的井的最早时间是多少。如果爬不出去，最多的生存时间是多少。
思路：
有几个状态，时间，高度，生命值，第几个垃圾。
时间显然是垃圾投入时就马上进行处理，所以这个应该不会是一维状态。
而一个垃圾只有两种状态，堆起来或者是吃掉，看起来就很像背包。
于是刚开始考虑的是用dp[i][j]表示处理前i个垃圾，剩余生命力是j的时候的最大高度。
但是这样j的取值范围并不是很好确定。
那么考虑用dp[i][j]表示处理前i个垃圾，当前高度是j时的最大生命力。
转移方程：dp[i][j] = max(dp[i-1][j-trash[i].h], dp[i-1][j]+trash[i].f)
要注意判断这个状态是不是可达的，也就是说生命力值是否超过了垃圾投入时间。
然后扫一遍得到答案。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<stack> 10 #include<queue> 11 #include<iostream> 12 13 #define inf 0x7fffffff 14 using namespace std; 15 typedef long long LL; 16 typedef pair<string, string> pr; 17 18 int d, n; 19 const int maxn = 105; 20 struct node{ 21 int t, f, h; 22 }trash[maxn]; 23 int dp[maxn][1005]; 24 25 bool cmp(node a, node b) 26 { 27 return a.t < b.t; 28 } 29 30 int main() 31 { 32 scanf("%d%d", &d, &n); 33 for(int i = 1; i <= n; i++){ 34 scanf("%d%d%d", &trash[i].t, &trash[i].f, &trash[i].h); 35 } 36 sort(trash + 1, trash + 1 + n, cmp); 37 //memset(dp, -1, sizeof(dp)); 38 dp[0][0] = 10; 39 40 int ans = 0, mxtime; 41 for(int i = 1; i <= n; i++){ 42 for(int j = 0; j <= d; j++){ 43 //if(dp[i][j] < 0)continue; 44 if(dp[i - 1][j] >= trash[i].t)dp[i][j] = max(dp[i][j], dp[i - 1][j] + trash[i].f); 45 if(j >= trash[i].h && dp[i - 1][j - trash[i].h] >= trash[i].t) dp[i][j] = max(dp[i - 1][j - trash[i].h], dp[i][j]); 46 //mxtime = max(dp[i][j], mxtime); 47 } 48 49 } 50 int maxh=0, maxt=0; 51 int i; 52 for(i=1;i<=n;i++) 53 { 54 for(int j=0;j<=d;j++) 55 { 56 if(dp[i][j]-trash[i].t>=0) 57 maxh=max(maxh,j); 58 maxt=max(maxt,dp[i][j]); 59 } 60 if(maxh==d) 61 break; 62 } 63 if(maxh==d) 64 cout<<trash[i].t<<endl; 65 else 66 cout<<maxt<<endl; 67 68 69 return 0; 70 }