中文题
f[i][j]代表第i个垃圾到高度j的时候的最大剩余生命值 （其实我一开始设置的是代表还能活时间j时的最大高度，但是这种方法转移时j的范围有点大）
方程就是 f[i][j]=max(f[i][j],f[i-1][j]-时间+生命,f[i-1][j-高度]-时间);(就是吃和不吃的决策)
这题的细节也很多
1.初始化为负无穷，并且f[0][0]=10 （这个比较小，基本没人错）
2.j-高度的决策时，要判断是否大于等于0 （这个是为了防止访问负下标）
3.一个垃圾在吃下之前，要保证垃圾掉落的时候还没死（就是说，决策 f[i-1][j]-时间+生命 的时候，要先判断f[i-1][j]-时间是否大于等于0）
4.出不去的时候，计算最高可到达高度的时候，也要特判3的情况（不然第十个点会过不去。。。）
#include <algorithm> #include <string> #include <string.h> #include <vector> #include <map> #include <stack> #include <set> #include <queue> #include <math.h> #include <cstdio> #include <iomanip> #include <time.h> #include <bitset> #include <cmath> #include <sstream> #include <iostream> #include <cstring> #define LL long long #define ls nod<<1 #define rs (nod<<1)+1 #define pii pair<int,int> #define mp make_pair #define pb push_back #define INF 0x3f3f3f3f const double eps = 1e-10; const int maxn = 2500 + 10; const LL mod = 1e9 + 7; int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} using namespace std; int f[maxn][maxn]; struct node { int t,f,h; bool operator < (const node &a) const { return t < a.t; } }q[maxn]; int main() { memset(f,-INF, sizeof(f)); ios::sync_with_stdio(false); int d,m; cin >> d >> m; int H = 0; for (int i = 1;i <= m;i++) { cin >> q[i].t >> q[i].f >> q[i].h; H += q[i].h; } sort(q+1,q+1+m); f[0][0] = 10; q[0].t = q[0].f = q[0].f = 0; for (int i = 1;i <= m;i++) { for (int j = 0;j <= H;j++) { if (f[i-1][j]-(q[i].t-q[i-1].t) >= 0) f[i][j] = max(f[i][j],f[i-1][j]-(q[i].t-q[i-1].t)+q[i].f); if (j >= q[i].h && f[i-1][j-q[i].h]-(q[i].t-q[i-1].t) >= 0) f[i][j] = max(f[i][j],f[i-1][j-q[i].h]-(q[i].t-q[i-1].t)); if (f[i][j] >= 0 && j >= d) { cout << q[i].t << endl; return 0; } } } int life=10; for (int i=1;i<=m;i++){ if (life-q[i].t+q[i-1].t<0){ printf("%d",q[i-1].t+life); return 0; } life=life-q[i].t+q[i-1].t+q[i].f; } printf("%d",q[m].t+life); return 0; }