垃圾陷阱
陈子骏
2018-04-02 19:29:12
```
//仍不是特别懂
#include<bits/stdc++.h>
using namespace std;
int dp[1001];
struct edg{
int t,h,p;
}a[1001];
int cmp(edg a,edg b)
{
return a.t<b.t;
}
int main()
{
int h,n;
scanf("%d%d",&h,&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a[i].t,&a[i].p,&a[i].h);
sort(a+1,a+n+1,cmp);
dp[0]=10;
for(int i=1;i<=n;i++)
for(int j=h;j>=0;j--)
{
if(dp[j]>=a[i].t)
{
if(j+a[i].h>=h)
{
printf("%d",a[i].t);
return 0;
}
dp[j+a[i].h]=max(dp[j],dp[j+a[i].h]);
dp[j]+=a[i].p;
}
}
printf("%d",dp[0]);
return 0;
}
```