【DP专题】——洛谷P1156垃圾陷阱

背包型动归。

传送门：GO

设f[i][j]表示第i个点高度为j的最大生命值。

如果吃掉：

f[i][j]=max(f[i-1][j]+t[i]-dis[i],f[i][j])

如果垫脚:

f[i][j]=max(f[i-1][j-h[i]]-dis[i],f[i][j])

如果有一种情况能让它走出去，就直接输出，

如果生命值小于0了，就直接跳过即可。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int read(){
 4     int x=0,f=1;
 5     char c=getchar();
 6     while(!isdigit(c)){
 7         if(c=='-') f=-1;
 8         c=getchar();
 9     }
10     while(isdigit(c)){
11         x=x*10+c-'0';
12         c=getchar();
13     }
14     return x*f;
15 }
16 const int N=110;
17 int d,n,ans;
18 struct bin{int time,life,h;}a[N];
19 bool cmp(bin t1,bin t2){return t1.time<t2.time;}
20 int t(int y){return a[y].time-a[y-1].time;}
21 int dp[N][N];
22 int main(){
23     d=read();
24     n=read();
25     for(int i=1;i<=n;i++){a[i]=(bin){read(),read(),read()};}
26     sort(a+1,a+n+1,cmp); 
27     memset(dp,-0x3f,sizeof(dp));
28     dp[0][0]=10;
29     ans=-0x7f;
30     for(int i=1;i<=n;i++){
31         for(int j=d;j>=0;j--){
32             if(dp[i-1][j]-t(i)<0) continue;
33             if(j+a[i].h>=d){
34                 printf("%d",a[i].time);
35                 return 0;
36             }
37             dp[i][j+a[i].h]=max(dp[i][j+a[i].h],dp[i-1][j]-t(i));
38             dp[i][j]=max(dp[i][j],dp[i-1][j]-t(i)+a[i].life);
39         }
40         ans=max(ans,dp[i][0]+a[i].time);
41     }
42     printf("%d",ans);
43     return 0;
44 }