洛谷 1156 垃圾陷阱
【题解】
考虑Dp. 设f[i][j]表示当前在第i个垃圾，高度为j，最多可以存活到什么时候。转移方程就是f[i][j]=max(f[i-1][j-h[i]], f[i-1][j]+a[i])
其中h[i]表示第i个垃圾能增加的高度，a[i]表示第i个垃圾能延长的存活时间，且能转移的条件是之前的f大于等于t[i]
注意要对t[i]排序后再处理。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N 2010 7 using namespace std; 8 int n,m,ans,f[N][N],h[N],a[N],t[N]; 9 struct rec{ 10 int h,a,t; 11 }s[N]; 12 inline int read(){ 13 int k=0,f=1; char c=getchar(); 14 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 15 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 16 return k*f; 17 } 18 inline bool cmp(rec a,rec b){return a.t<b.t;} 19 int main(){ 20 m=read(); n=read(); 21 for(rg int i=1;i<=n;i++) s[i].t=read(),s[i].a=read(),s[i].h=read(); 22 sort(s+1,s+1+n,cmp); 23 f[0][0]=10; 24 for(rg int i=1;i<=n;i++){ 25 for(rg int j=2500;j>=0;j--){ 26 if(j>=s[i].h&&f[i-1][j-s[i].h]>=s[i].t) f[i][j]=max(f[i][j],f[i-1][j-s[i].h]); 27 if(f[i-1][j]>=s[i].t) f[i][j]=max(f[i][j],f[i-1][j]+s[i].a); 28 if(j>=m&&f[i][j]>=s[i].t){ 29 printf("%d ",s[i].t); return 0; 30 } 31 ans=max(ans,f[i][j]); 32 } 33 } 34 printf("%d ",ans); 35 return 0; 36 }