卡门堆放她收到的第一个垃圾: height=9;
卡门吃掉她收到的第二个垃圾, 使她的生命从 10 小时延伸到 13 小时;
卡门堆放第 3 个垃圾, height=19; 卡门堆放第 4 个垃圾, height=20
如果出不去, 就直接全部吃掉
最优解: 相同高度活更久
依题意得: dp[0]=10;
- #include <bits / stdc++.h>
- using namespace std;
- int dp[1001];
- struct node {
- int t,
- f,
- h;
- }
- s[1001];
- bool cmp(node a, node b) {
- return a.t <b.t;
- }
- int main() {
- ios: :sync_with_stdio(false);
- int n,
- g,
- i,
- j;
- cin>> n>> g;
- for (i = 0; i <g; i++) {
- cin>> s[i].t>> s[i].f>> s[i].h;
- }
- sort(s, s + g, cmp);
- dp[0] = 10;
- for (i = 0; i <g; i++) // 遍历全部
- for (j = n; j>= 0; j--) {
- if (dp[j]>= s[i].t) { // 活过这个时间
- if (s[i].h + j>= n) { //
- cout << s[i].t << endl;
- return 0;
- }
- dp[j + s[i].h] = max(dp[j + s[i].h], dp[j]); // 不吃, 堆起来
- dp[j] += s[i].f; // 吃掉
- }
- }
- cout << dp[0] << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2529515.html