题意：
卡门——农夫约翰极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D (2 <= D <= 100)英尺。
卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间t(0<t<=1000)，以及每个垃圾堆放的高度h(1<=h<=25)和吃进该垃圾能维持生命的时间f(1<=f<=30)，要求出卡门最早能逃出井外的时间，假 设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。
思路：
dp。。。
f数组为状态转移数组,H数组为第i个的高度，T为第i个下落的时间,F为第i个提供的生命值。
转移方程为：
f[i][j+H(i)]=f[i-1][j]-T(i)+T(i-1) (f[i-1][j]-T(i)+T(i-1)>=0 即奶牛在第i个垃圾下来时还活着)//这个方程是使用垃圾的情况
f[i][j]=max(f[i][j],f[i-1][j]-T(i)+T(i-1)+F(i)) (条件跟上一个一样) //这个方程是吃垃圾的情况
如果转移时发现f[i-1][j]-T(i)+T(i-1)>=0且j+H(i)>n (n为陷阱的深度) 那么就说明奶牛出坑了。
如果完成全部状态转移之后，奶牛还没有出坑，就说明他出不了坑，那么他就应该放弃治疗去吃垃圾。。。
最后可以用滚动数组压缩空间
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define MAXN 1100 7 struct Node{ 8 int t,h,f; 9 Node(){} 10 Node(int t,int h,int f):t(t),h(h),f(f){} 11 }tmp; 12 Node nums[MAXN]; 13 int f[2][MAXN]; 14 int i,j,k,m,n,t,h; 15 void qsort(int l,int r){ 16 int i=l,j=r,mid=nums[(i+j)>>1].t; 17 while(i<=j){ 18 while(nums[i].t<mid) i++; 19 while(nums[j].t>mid) j--; 20 if(i<=j){ 21 tmp=nums[i]; 22 nums[i]=nums[j]; 23 nums[j]=tmp; 24 i++,j--; 25 } 26 } 27 if(l<j) qsort(l,j); 28 if(r>i) qsort(i,r); 29 } 30 int main(){ 31 #ifndef ONLINE_JUDGE 32 freopen("well.in","r",stdin); 33 freopen("well.out","w",stdout); 34 #endif 35 scanf("%d%d",&n,&m); 36 for(i=1;i<=m;i++){ 37 scanf("%d%d%d",&t,&k,&h); 38 nums[i]=Node(t,h,k); 39 } 40 qsort(1,m); 41 memset(f,-1,sizeof(f)); 42 f[1][0]=10; nums[0]=Node(0,0,0); 43 for(i=1;i<=m;i++){ 44 for(j=0;j<=n;j++) f[(i+1)%2][j]=-1; 45 for(j=0;j<=n;j++){ 46 if(f[(i)%2][j]<0) continue; 47 if(f[i%2][j]-nums[i].t+nums[i-1].t>=0&&j+nums[i].h>=n){ 48 printf("%d\n",nums[i].t); 49 return 0; 50 } 51 if(f[i%2][j]-nums[i].t+nums[i-1].t>=0) { 52 f[(i+1)%2][j+nums[i].h]=f[i%2][j]-nums[i].t+nums[i-1].t; 53 f[(i+1)%2][j]=max(f[(i+1)%2][j],f[i%2][j]-nums[i].t+nums[i-1].t+nums[i].f); 54 } 55 } 56 } 57 k=10; 58 nums[m+1]=Node(MAXN*1000,0,0); 59 for(i=1;i<=m+1;i++){ 60 if((k=k-nums[i].t+nums[i-1].t)<0){ 61 printf("%d\n",nums[i].t+k); 62 break; 63 } 64 k+=nums[i].f; 65 } 66 return 0; 67 } 68 /* 69 20 4 70 5 4 9 71 9 3 2 72 12 6 10 73 13 1 1 74 75 */
原文：https://www.cnblogs.com/linxif2008/p/9691709.html