P1156 垃圾陷阱

发表于 | 更新于
本文字数： 4.2k | 阅读时长 ≈ 4 分钟

题意：d深，10能量，一小时能量减一，n个物品有投入时间，高度，能量的属性，问何时可以达到d深或最长时间

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
#include<bits/stdc++.h>
using namespace std;
struct data{
	int t,f,h;
}ct[2001];
bool cm(data a,data b){
	return a.t<b.t;
}
int dp[200]={10};//到i高度还有多少时间 
int d,g,t,dnow;
int main(){
	ios::sync_with_stdio(0);
	cin>>d>>g;
	for(int i=1;i<=g;i++)
		cin>>ct[i].t>>ct[i].f>>ct[i].h;
	sort(ct+1,ct+g+1,cm);
	for(int i=1;i<=g;i++){
		for(int j=d;j>=0;j--){
			if(dp[j]>=ct[i].t){
				if(j+ct[i].h>=d){
					cout<<ct[i].t;
					return 0;
				}
				dp[j+ct[i].h]=max(dp[j+ct[i].h],dp[j]);
				dp[j]+=ct[i].f;
			}
		}
	}
	cout<<dp[0];
	return 0;
}