题解
太妙了
如果能出去,那么出去的时间一定为让我出去的那个垃圾掉落的时间,且在此之前我所在的高度能撑到我垃圾掉落
如果出不去,我肯定一直呆在井底不动
所以我们可以以高度为变量 设每个高度能撑到的最久的时间
而每个垃圾在拿到的一瞬间要么吃要么搭,所以我们穷举,两个都要,如果搭,那么搭上去的高度更新,如果吃,现在的高度更新
如果从高度高到低遍历是不会有重复的计算
避免二的次方级别运算的核心是对达到的每个高度取舍,取能坚持最久的那套方案
code
#include<bits/stdc++.h>
using namespace std;
struct unit
{
int t,heal,h;
}r[105];
bool cmp(unit a,unit b)
{
return a.t<b.t;
}
int last[105]={0};//代表当前高度最多能撑到什么时候
int main()
{
int height,n;
cin>>height>>n;
for(int i=1;i<=n;i++) cin>>r[i].t>>r[i].heal>>r[i].h;
sort(r+1,r+n+1,cmp);
last[0]=10;
for(int i=1;i<=n;i++)
{
for(int h=height;h>=0;h--)
{
if(last[h]>=r[i].t)//如果能撑到垃圾到来
{
if(h+r[i].h>=height)//瞬间开溜
{
cout<<r[i].t;
return 0;
}
last[h+r[i].h]=max(last[h+r[i].h],last[h]);//每个垃圾都有两个去处
last[h]+=r[i].heal;
}
}
}
cout<<last[0];
return 0;
}
标签:能撑,int,高度,垃圾,陷阱,P1156,unit
From: https://www.cnblogs.com/pure4knowledge/p/18051006