思路
用 f [ i ] [ j ] 来表示第 i 个垃圾被扔下时垃圾堆的高度为 j 时能活下去的时间。
一开始考虑在 j 枚举时间，结果T掉了一个点，反而在高度为１～１００的情况下枚举高度更方便。
给时间先排序 ( 数据里给出的并不是升序的时间线 ) , 就能保证如果牛能活 ( 注意牛有濒死状态, 也就是 0 血的时候还能秀) 到扔下第 i + 1 个垃圾时, 如果垃圾高度够了此时耗费的时间是最优的.
如果不行的话就让牛一直吃, 找到他最多能活到什么时候.
CODE
#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
namespace _buff {
const size_t BUFF = 1 << 19;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
if (ib == ie) {
ib = ibuf;
ie = ibuf + fread(ibuf, 1, BUFF, stdin);
}
return ib == ie ? -1 : *ib++;
}
}
int qread() {
using namespace _buff;
int ret = 0;
bool pos = true;
char c = getc();
for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
assert(~c);
}
if (c == '-') {
pos = false;
c = getc();
}
for (; c >= '0' && c <= '9'; c = getc()) {
ret = (ret << 3) + (ret << 1) + (c ^ 48);
}
return pos ? ret : -ret;
}
const int maxn = 1007;
int d, g;
struct node{
int t, f, h;
} a[maxn];
int f[maxn][maxn];
bool cmp(node a, node b) {
return a.t < b.t;
}
int main()
{
read(d);read(g);
for ( int i = 1; i <= g; ++i ) {
read(a[i].t);
read(a[i].f);
read(a[i].h);
}
sort(a + 1, a + g + 1, cmp);
f[0][0] = 10;
a[0] = {0, 0, 0};
for ( int i = 0; i < g; ++i ) {
for ( int j = 0; j <= d; ++j ) {
if(f[i][j] >= a[i + 1].t) {
int new_high = j + a[i + 1].h;
if(new_high >= d) {
printf("%d
",a[i + 1].t);
return 0;
}
f[i + 1][j] = max(f[i + 1][j], f[i][j] + a[i + 1].f);
f[i + 1][new_high] = max(f[i + 1][new_high], f[i][j]);
}
}
}
int ans = INT_MIN;
for ( int i = 1; i <= g; ++i ) {
ans = max(ans, f[i][0]);
}
cout << ans << endl;
return 0;
}