P1156 垃圾陷阱 传送门
思路：
设 f [ i ][ j ] 表示，扔进去 i 个垃圾，垃圾高度为 j 时，奶牛的生命值。
初始化 f 数组为 -1，因为当奶牛生命值为 0 时，奶牛还是可以操纵垃圾。f [ 0 ][ 0 ] = 10 为奶牛的初始生命值。
转移如下：
① 当 f [ i ][ j ] < 0 时，说明这个状态奶牛已经死了，跳过。
② 当 f [ i ][ j ] = 0 时，奶牛处于濒死状态，还可以操作，必须吃掉垃圾。进而判断这个垃圾恢复的生命值是否能够支撑到下一个垃圾的投入，若不能，就跳过，否则就转移状态。
③ 当 f [ i ][ j ] > 0 时，判断奶牛不吃这个垃圾的生命值能否支撑到下一个垃圾的投入，能，就把垃圾堆起来。不能，就吃掉。吃掉后再判断能否转移，同 ② 。
伪代码：
struct hh { LL tim,w,h;//tim垃圾投入的时间、w垃圾恢复的生命值、h垃圾的高度 }t[maxn];
f[0][0]=10; for(LL i=0;i<g;i++)//第一重循环，枚举投入的垃圾 for(LL j=0;j<=d;j++)//枚举高度 { if(f[i][j]<0) continue;//如果奶牛无法到达这个状态，跳过 if(j+t[i+1].h>=d&&f[i][j]>=t[i+1].tim-t[i].tim)//判断奶牛在不吃这个垃圾的状态下，能否跳出陷阱 { out(t[i+1].tim);return 0; } if(f[i][j]-t[i+1].tim+t[i].tim>=0)//同时判断、转移②，③两种情况 { f[i+1][j+t[i+1].h]=f[i][j]-t[i+1].tim+t[i].tim; f[i+1][j]=lck_max(f[i+1][j],f[i][j]-t[i+1].tim+t[i].tim+t[i+1].w); } }
标程：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<cstdlib> #include<stack> #include<vector> #include<queue> #include<deque> #include<map> #include<set> using namespace std; #define lck_max(a,b) ((a)>(b)?(a):(b)) #define lck_min(a,b) ((a)<(b)?(a):(b)) typedef long long LL; #define maxn 1001 LL d,g,ans,las,f[maxn][maxn]; struct hh { LL w,h,tim; }t[maxn]; inline LL read() { LL kr=1,xs=0; char ls; ls=getchar(); while(!isdigit(ls)) { if(!(ls^45)) kr=-1; ls=getchar(); } while(isdigit(ls)) { xs=(xs<<1)+(xs<<3)+(ls^48); ls=getchar(); } return xs*kr; } inline void out(LL xs) { if(!xs) {putchar(48); return;} if(xs<0) putchar('-'),xs=-xs; int kr[57],ls=0; while(xs) kr[++ls]=xs%10,xs/=10; while(ls) putchar(kr[ls]+48),ls--; } inline bool cmp(const hh&a,const hh&b) { return a.tim<b.tim; } int main() { freopen("ljxj.in","r",stdin); freopen("ljxj.out","w",stdout); d=read();g=read(); for(LL i=1;i<=g;i++) { t[i].tim=read();t[i].w=read();t[i].h=read(); } sort(t+1,t+g+1,cmp); memset(f,-1,sizeof(f)); f[0][0]=10; for(LL i=0;i<g;i++) for(LL j=0;j<=d;j++) { if(f[i][j]<0) continue; if(j+t[i+1].h>=d&&f[i][j]>=t[i+1].tim-t[i].tim) { out(t[i+1].tim);return 0; } if(f[i][j]-t[i+1].tim+t[i].tim>=0) { f[i+1][j+t[i+1].h]=f[i][j]-t[i+1].tim+t[i].tim; f[i+1][j]=lck_max(f[i+1][j],f[i][j]-t[i+1].tim+t[i].tim+t[i+1].w); } } for(LL i=1;i<=g;i++) { if(t[i].tim-t[i-1].tim>f[0][0]) break; ans+=t[i].tim-t[i-1].tim; f[0][0]-=t[i].tim-t[i-1].tim; f[0][0]+=t[i].w; } ans+=f[0][0]; out(ans); return 0; }