【洛谷习题】垃圾陷阱

题目链接：https://www.luogu.org/problemnew/show/P1156

一开始做的时候看着挺像背包，但背包也没有取了一个会对之后取别的有影响的啊。谁知道正解的确是看成背包。

我们可以以深度为容量，垃圾高度为重量，时间为价值，然后就像01背包那样讨论取或不取就可以了。当然，我们需要保证垃圾按时间排好序。

但和普通的01背包不同，这里并非简单的取或不取，而是堆起来还是吃掉，因此不会像不取那样直接不操作。

1 if (dp[i - 1][j] >= trash[i].t)
2     dp[i][j] = max(dp[i][j], dp[i - 1][j] + trash[i].f);
3 if (j >= trash[i].h && dp[i - 1][j - trash[i].h] >= trash[i].t)
4     dp[i][j] = max(dp[i][j], dp[i - 1][j - trash[i].h]);

像这样，若是第i个垃圾堆吃掉了，那么他应该是操作完第i-1个垃圾堆后，且高度未变，再加上第i堆垃圾堆的价值。如果是堆起来了，那么应该是从操作完第i-1堆垃圾，高度为当前高度减第i堆垃圾时转移过来的。

我们每次都保证价值最大，那么第一次遇到堆够D（此时价值必不为0），就是答案。另外，若是出不去，那么过程中最大的dp[i][j]就是答案。

这道题改成一维空间并不容易，可能也并不可行，而且该题也不需要。

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 const int maxg = 105, maxd = 105;
 7 
 8 struct Trash {
 9     int t, f, h;
10     bool operator < (const Trash& rhs) const {
11         return t < rhs.t;
12     }
13 } trash[maxg];
14 
15 int d, g, dp[maxg][maxd], ans;
16 
17 int main() {
18     scanf("%d%d", &d, &g);
19     for (int i = 1; i <= g; ++i)
20         scanf("%d%d%d", &trash[i].t, &trash[i].f, &trash[i].h);
21     sort(trash + 1, trash + g + 1);
22     dp[0][0] = 10;
23     for (int i = 1; i <= g; ++i)
24         for (int j = 0; j <= d; ++j) {
25             if (dp[i - 1][j] >= trash[i].t)
26                 dp[i][j] = max(dp[i][j], dp[i - 1][j] + trash[i].f);
27             if (j >= trash[i].h && dp[i - 1][j - trash[i].h] >= trash[i].t)
28                 dp[i][j] = max(dp[i][j], dp[i - 1][j - trash[i].h]);
29             if (j == d && dp[i][j]) {printf("%d", trash[i].t);return 0;}
30             ans = max(ans, dp[i][j]);
31         }
32     printf("%d", ans);
33     return 0;
34 }

AC代码

【洛谷习题】垃圾陷阱

相关推荐