https://www.luogu.com.cn/problem/P1156

题目描述

卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为 D(2≤D≤100) 英尺。

卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间 t(0<t≤1000)，以及每个垃圾堆放的高度 h(1≤h≤25)和吃进该垃圾能维持生命的时间 f(1≤f*≤30)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。

输入格式

第一行为2个整数，D 和 G(1≤ G≤100)，G为被投入井的垃圾的数量。

第二到第 G+1 行每行包括 3个整数：T(0<T<=1000)，表示垃圾被投进井中的时间；F(1≤F≤30)，表示该垃圾能维持卡门生命的时间；和 H(1≤H≤25)，该垃圾能垫高的高度。

输出格式

如果卡门可以爬出陷阱，输出一个整表示最早什么时候可以爬出；否则输出卡门最长可以存活多长时间。

输入输出样例

输入 #1

1
2
3
4
5
20 4
5 4 9
9 3 2
12 6 10
13 1 1

输出 #1

1
13

$d[i][j]$ 表示前 i 个垃圾，高度为 j 时的最大存活时间（累计）。转移方程：

  1. $f[i][j]=max(f[i][j],f[i-1][j] + F) $
  2. $f[i][j+H]=f[i-1][j]$

因为 2 . 的关系 $f[i][j]$ 可能提前更新，所以要取 $\max()$ 。

如果无法到达顶部，因为有可能无法等到下一个垃圾到来就死了…所以不能直接输出 sum…

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
const int MAX=100+10;
int d,g,cur,f[MAX][MAX],T,F,H,sum,ans=INF;
struct node{
	int t,f,h;
	bool operator<(const node&x)const{
		return t<x.t;
	}
}a[MAX];
int main(){
	freopen("in","r",stdin);
	sf(d);sf(g);
	fi(i,0,g){
		sf(a[i].t);sf(a[i].f);sf(a[i].h);
		sum+=a[i].f;
	}
	sort(a,a+g);
	f[0][0]=10+a[0].f;
	f[0][a[0].h]=10;
	fi(i,1,g){
		T=a[i].t;F=a[i].f;H=a[i].h;
		fi(j,0,d+1){
			if(f[i-1][j] >= T) {
				f[i][j]=max(f[i][j],f[i-1][j] + F);//因为下面那句可能提前更新g[i][j]所以需要 max()
				f[i][j+H]=f[i-1][j];
				if(j+H>=d) {
					ans=min(ans,f[i][j+H]);
				}
			}  
		}
	}
	if(ans==INF){
		ans=0;
		fi(i,0,g)ans=max(ans,f[i][0]);
		pf(ans);
	}else pf(ans);
	return 0;  
}