P1156 垃圾陷阱

本文主要是介绍P1156 垃圾陷阱，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接 ~~~~~      总题单链接
~~~~~      这道题的关键在于：你不能在死了之后通过吃东西复活，所以我们在状态转移的时候只转移活着的状态。
~~~~~      先考虑第一问：最早什么时候可以爬出。将物品按时间排序，用 $f_i$ 表示吃了第 $i$ 个物品能续命多久，$h_i$ 表示能搭多高。设 $d{p}_i$ 表示生命值为 $i$ 的情况下的最大高度，对于每个物品有两种选择——吃或搭。如果选搭，$dp[i]=max(dp[i],dp[i]+h)$ 即 $dp[i]=dp[i]+h$，如果选择吃 $dp[i+f]=max(dp[i+f],dp[i])$。
~~~~~      再来看第二问：最长可以存活多长时间。那就是要全选择吃，贪心即可。

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
using namespace std;ll d,g,dp[3005],mx=10;// 时间，f，h 
pair<ll,pair<ll,ll>>c[105];signed main(){ios::sync_with_stdio(false);cin>>d>>g;for(ll i=1;i<=g;i++)cin>>c[i].fir>>c[i].sec.fir>>c[i].sec.sec;sort(c+1,c+1+g);memset(dp,-0x3f,sizeof(dp));for(ll i=1;i<=10;i++)dp[i]=0;for(ll i=1;i<=g;i++){ll t=c[i].fir,x=c[i].sec.fir,y=c[i].sec.sec;if(mx>=t)mx+=x;for(ll j=3000-x;j>=t;j--){dp[j+x]=max(dp[j+x],dp[j]);dp[j]+=y;}for(ll j=1;j<=3000;j++){if(dp[j]>=d){cout<<t;return 0;}}}cout<<mx<<endl;return 0;
}

这篇关于P1156 垃圾陷阱的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---