一道简单的动态规划
将每个垃圾按扔下来的时间从小到大排序
每次扔下来一个垃圾时，如果能靠这个垃圾爬出来就1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
不然就继续
最后如果挂了的话算一下他能撑多久
```cpp
#include <bits/stdc++.h>
const int MaxN = 100010;
struct node
{
int t, f, h;
};
node a[MaxN];
int d, g, f[MaxN];
inline int cmp(node a, node b)
{
return a.t < b.t;
}
inline int read()
{
int x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
int main()
{
d = read(), g = read();
for (int i = 1; i <= g; i++)
a[i].t = read(), a[i].f = read(), a[i].h = read();
std::sort(a + 1, a + g + 1, cmp);
f[0] = 10;
for (int i = 1; i <= g; i++)
{
for (int j = d; j >= 0; j--)
{
if (f[j] >= a[i].t)
{
if (j + a[i].h >= d)
return 0 * printf("%d\n", a[i].t);
f[j + a[i].h] = std::max(f[j], f[j + a[i].h]);
f[j] += a[i].f;
}
}
}
printf("%d\n", f[0]);
return 0;
}