我是真的不知道。。。
这道题对于每一个垃圾有两个决策：堆放不吃 或者 吃掉不堆放。
终止条件是堆放的高度达到\(d\)。想要求达到状态的最大生命值或者最久能活到多久。
可以联想到背包问题，而且是01背包。
把生命值当做价值，把高度当做重量，我们就可以用最小重量取出最大价值。
设\(dp[i][j]\)为前\(i\)个垃圾，已经堆放了高度\(j\)的最大生命值。
递推就可以想普通的填表法搞出来。
这个东西挺奇怪的，奶牛生命值为0的时候还能转移。。。这个注意一下。
如果填表的时候填到\(j==n\)的时候就可以判断是可以出去的，直接return掉。
否则要输出奶牛能活最久多长时间。我们可以利用dp数组，求出的最大生命值加上那一块掉落时间。
注意：在做dp的时候，有的dp是没有状态的，是会死的。这些死的dp值是负数。
所以我们要初始化dp数组为负无穷大。
注意：给你的垃圾顺序可能是乱序的，要按照时间顺序排序。
代码：
#include#include #include const int maxn = 105;const int INF = 0x3f3f3f3f;int d, g;struct Trash{ int tim, t, h;} s[maxn];int dp[maxn][maxn];// 前i件垃圾，堆了高度j的最大生命值 int read(){ int ans = 0, s = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') s = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') ans = (ans << 3) + (ans << 1) + ch - '0', ch = getchar(); return s * ans;}bool cmp(const Trash a, const Trash b){ return a.tim < b.tim;}int main(){ d = read(), g = read(); for(int i = 1; i <= g; i++) { s[i].tim = read(), s[i].t = read(), s[i].h = read(); } for(int i = 0; i <= g; i++) for(int j = 0; j <= d; j++) dp[i][j] = -INF; std::sort(s + 1, s + g + 1, cmp); dp[0][0] = 10; for(int i = 1; i <= g; i++) { for(int j = 0; j <= d; j++) { if(dp[i - 1][j] - (s[i].tim - s[i - 1].tim) >= 0)// 没被饿死 { dp[i][j] = std::max(dp[i][j], dp[i - 1][j] - (s[i].tim - s[i - 1].tim) + s[i].t); } if(dp[i - 1][j - s[i].h] - (s[i].tim - s[i - 1].tim) >= 0 && j - s[i].h >= 0)// 没被饿死，并且能转移 { dp[i][j] = std::max(dp[i][j], dp[i - 1][j - s[i].h] - (s[i].tim - s[i - 1].tim)); if(j == d) { printf("%d\n", s[i].tim); return 0; } } } } int ans = -INF; for(int i = 1; i <= g; i++) { for(int j = 0; j <= d; j++) { if(dp[i][j] < 0) continue; ans = std::max(ans, dp[i][j] + s[i].tim); } } printf("%d\n", ans); return 0;}