本题为3月21日23上半学期集训每日一题中A题的题解
题面
题目描述
卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D( \(2\leq D\leq 100\))英尺。
卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间t( \(0 < t\leq 1000\) )，以及每个垃圾堆放的高度h( \(1 \leq h \leq 25\) )和吃进该垃圾能维持生命的时间f( \(1 \leq f \leq 30\) )，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。
输入
第一行为2个整数，D和 G ( \(1 \leq G \leq 100\) )，G为被投入井的垃圾的数量。
第二到第G+1行每行包括3个整数：T ( \(0 < T \leq 1000\) )，表示垃圾被投进井中的时间；F ( \(1 \leq F \leq 30\) )，表示该垃圾能维持卡门生命的时间；和 H( \(1 \leq H \leq 25\) )，该垃圾能垫高的高度。
输出
如果卡门可以爬出陷阱，输出一个整表示最早什么时候可以爬出；否则输出卡门最长可以存活多长时间。
样例输入
20 4
5 4 9
9 3 2
12 6 10
13 1 1
样例输出
13
提示
样例说明:
卡门堆放她收到的第一个垃圾：height=9；
卡门吃掉她收到的第2个垃圾，使她的生命从10小时延伸到13小时；
卡门堆放第3个垃圾，height=19；
卡门堆放第4个垃圾，height=20。
思路分析
此题很像背包问题,只是此处如果不堆垃圾的话还能吃垃圾.所以我们考虑一下能否用动态规划求解.
首先,时间是一个不需要考虑的因素,因为每一堆垃圾都是在某一时刻落下的,所以垃圾就对应着时间.
然后,这里有两个量,一个是垃圾堆放的高度,一个是存活的时间.那么选择哪个作为状态呢?答案是都可以!我们可以把状态定义成垃圾堆放的高度,把血量作为一个递推的维度(类似背包问题的处理).我们也可以考虑把剩余血量定义成状态,堆放高度作为一个递推的维度(类似多重部分和问题的处理).但是从时间和空间上来考虑,由于此题血量的最大值可能很大,把它作为一个递推维度是不如作为状态的,所以我们这里选择将堆放高度作为一个维度,将剩余血量定义为状态.这样就可以按照类似多重部分和问题的方式来处理(仅是类似,多重部分和问题中状态每次只会减1,且并不会增加).如果你想要试试另一种做法,可以参考洛谷上的这篇题解.
定义好状态之后,接下来就来解决状态转移方程.如果一个垃圾不拿来堆的话,为了收益最大,我们会拿来吃,因此我们只需要分开递推这两种即可.
在还活着的情况下,如果当前垃圾用来吃,那么就增加当前高度的剩余存活时间,所以目前得出的转移方程为: \(dp[i][j] = dp[i][j - 1] - \Delta t + f[i] (\Delta t = t[i] - t[i - 1],后略)\) .如果当前垃圾用来填,那么也就是说 \(j + h[i]\) 这个状态在此之后是可以出现的(在这之前这个状态可能是没有的,因为可能还没有填充到这个高度),我们将这个状态开辟出来.由于没有吃,此时这个状态的值就是当前剩余的存活时间,所以状态转移方程为 \(dp[i][j + h[i]] = dp[i][j - 1] - \Delta t\).
由于我们开辟状态的时候会使得 \(dp[i][j + h[i]]\) 中存放一个有意义的值,而后续我们在计算 \(j + h[i]\) 的时候,如果选择吃,可能需要保留这个值,所以吃垃圾的状态转移方程应修改为 \(dp[i][j] = max(dp[i][j], dp[i][j - 1] - \Delta t+ f[i])\) .
那么,什么时候是死了捏?显然,当 \(dp[i][j - 1] < \Delta t\) 时,即当前血量已被扣完(因为我们当前处理的是这一秒,当血量为0时是这一秒结束之后死,所以当前还没死,可以继续处理),这个时候当前状态不可达到,直接跳过不处理即可.
那么,什么时候是逃出去了捏?显然,当高度可达的状态大于等于d时,就是逃出去了,也就是 \(j + h[i] \geq d\) (即当前开辟出来的状态的高度是大于等于高度上限的).这时我们输出当前i的时间然后终止程序即可.
那么,什么时候是没逃出去捏?当然是没逃出去喽状态转移成功结束了,因为一旦中途出去了,程序就会被终止.此时根据题目要求,我们需要改求最长存活时间.这里最简单的解决方法是重新处理一遍,这次全部吃垃圾.这时没必要用数组来递推,我们维护两个变量,一个sum存放最长存活时间,另一个now存放当前还能活多久.然后在还能活的情况下,遍历每一个垃圾,让sum加上 \(\Delta t\) ,再更新now.如果不能活了或者全部遍历完了,那这就是最大时间,输出sum + now即可.
此题数据量较小,无需继续优化空间.如果你愿意,还可以像01背包问题那样利用滚动数组进行空间优化.
参考代码
时间复杂度: \(O(GD)\)
空间复杂度: \(O(GD)\)
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
// 此处不能用goto,故定义一个宏
#define end \
delete[] rub; \
return 0;
// 垃圾对象
struct node {
int t = 0, h, f;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int d, g;
cin >> d >> g;
// 输入各个垃圾
node *rub = new node[g + 1];
for (int i = 1; i <= g; i++) {
cin >> rub[i].t >> rub[i].f >> rub[i].h;
}
// 按时间升序排序
sort(rub, rub + g + 1, [](node a, node b) { return a.t < b.t; });
// 动态规划
vector<vector<int>> dp(g + 1, vector<int>(d + 1, -1)); // 第一维表示当前垃圾,第二维表示当前堆叠高度.
dp[0][0] = 10;
// 状态转移
for (int i = 1; i <= g; i++) {
int dt = rub[i].t - rub[i - 1].t; // 当前变化时间
for (int j = 0; j <= d; j++) {
if (dp[i - 1][j] >= dt) { // 还活着
if (j + rub[i].h >= d) { // 能开辟大于等于上限的堆叠高度,表示可以出去了
cout << rub[i].t << "\n";
end;
}
dp[i][j + rub[i].h] = dp[i - 1][j] - dt; // 填,开辟新的状态
dp[i][j] = max(dp[i][j], dp[i - 1][j] - dt + rub[i].f); // 吃,补充剩余时间
}
}
}
// 全吃
int sum = 0, now = 10; // 记得初始时有10的时间
for (int i = 1; i <= g; i++) {
int dt = rub[i].t - rub[i - 1].t; // 当前变化时间
if (dt > now) { // 死了,当前是最长存活时间
cout << sum + now << "\n";
end;
}
sum += dt; // 更新已存活时间
now = now - dt + rub[i].f; // 维护剩余时间
}
cout << sum + now << "\n";
end;
}
"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德