Leetcode第451场周赛分析总结

在这里插入图片描述

题目链接

竞赛 - 力扣（LeetCode）全球极客挚爱的技术成长平台

题目解析

A. 3560. 木材运输的最小成本

AC代码

class Solution {
public:long long minCuttingCost(int n, int m, int k) {if (n > m) swap(n, m);  // n <= m;using ll = long long;ll ans = 0;if (m > k) {ans = static_cast<ll>(k) * (m - k);}return ans;}
};

思路分析

看完题目后发现，只有三辆车，题目保证有解，意味着最多只有一根木棍的长度会大于k从而被切割。接下来问题转换为，给定一根长度为n>k的木棍，将其切割为x+y=n两部分，求z=x*y的最小值。我记得这是初中常见的一个约束，最大值出现在x=y=n/2的位置，最小值出现在两端。实际上z是x的一个二次函数，在其作用域内先增加后减少。

x的最大值是k，那么z的最小值就是k*(n-k)。

可惜在实现的时候没注意乘积会导致爆long long。其实返回值是long long就应该注意到的，不太应该。

灵神用Python代码一行就搞定了。Python的int操作起来是更方便一些。在算法竞赛有时会遇到一些大数运算（超过long long范围的运算），如果用C++需要手动模拟实现，用Python就方便很多。

Python的int类型可以处理任意精度的整数，理论上没有固定的大小限制，仅受限于计算机的可用内存（RAM）。

B. 3561.移除相邻字符

AC代码

class Solution {bool aux(char x, char y) {int diff = abs(x - y);return diff == 1 || diff == 25;}
public:string resultingString(string s) {string stk;for (auto c : s) {if (stk.empty()) {stk.push_back(c);} else {if (aux(stk.back(), c)) {stk.pop_back();} else {stk.push_back(c);}}}return stk;}
};

思路分析

注意到对于每次消除，至多影响前面的一个元素。每次都移除最左边的字符对，模拟了一下发现类似栈的性质，用栈模拟。

灵神的代码是先统一入栈，再考虑能否消除，在逻辑和实现上更简洁一些。

C. 3562. 折扣价交易股票的最大利润

AC代码

class Solution {
public:int maxProfit(int n, vector<int>& present, vector<int>& future, vector<vector<int>>& hierarchy, int budget) {vector<vector<int>> graph(n);for (auto &edge : hierarchy) {int u = edge[0] - 1, v = edge[1] - 1;graph[u].push_back(v);}function<vector<vector<int>>(int)> dfs;dfs = [&](int u) -> vector<vector<int>> {vector f(budget + 1, vector<int>(2, 0));vector g = f;for (int v : graph[u]) {auto fv = dfs(v);for (int b = budget; b >= 0; b--) {for (int bv = 0; bv <= b; bv++) {for (int k = 0; k < 2; k++) {g[b][k] = max(g[b][k], g[b - bv][k] + fv[bv][k]);}}}}for (int b = 0; b <= budget; b++) {for (int k = 0; k < 2; k++) {int bu = present[u] / (k + 1);if (bu <= b) {f[b][k] = max(g[b][0], g[b - bu][1] + future[u] - bu);} else {f[b][k] = g[b][0];}}}return f;};return dfs(0)[budget][0];}
};

思路分析

比赛时想到如果员工的关系是一个链表，那我可以类似背包问题进行处理，对于每由于每个员工只影响自己的下属（不会影响领导），所以有无后效性。需要最大化收益，所以有最优子结构。

每个员工有两个状态：

可以使用的最大费用 $b$
领导是否购买股票 $k$ ：0表示不买，1表示买

维护每个员工 $u$ 在给定状态 $(b, k)$ 下他和下属可以获得的最大收益 $f$ ， $v$ 表示他的下属， $c_k$ 表示在领导买股票状态为 $k$ 的情况下购买股票的费用， $p_k$ 表示购买股票的收益。

$f_u(b,k)= max\{f_v(b,0), f_v(b-c_k, 1)+p_k\}$

然后就可以进行状态转移。可是面对一个树结构，如果某员工决定给 $t$ 个下属 $b$ 费用让他们买股票，每个下属应该用多少费用才能获得最大收益呢？感觉得再需要一个回溯去搜索，简单想了一下会超时。

在认真听了灵神的讲解后，发现自己对背包问题的理解还是太浅显。

现在让我们专心考虑这个子问题，我们可以先得到每个下属在所有状态下的收益 $f_{v}(b,k)$ （因为是在DP中），那对于某员工有 $b$ 费用的情况下，我们考虑前 $i$ 下属消耗多少费用才能获得最大收益 $g_i(b,k)$

之所以考虑前 $i$ 个是因为员工之间的选择除了消耗费用没有额外的影响，因此无后效性，求最大收益所以有最优子结构。我们发现，员工对他们下属的费用选择形成了一个0-1背包问题，不过与普通背包问题不同的是，每个物品的价格和收益不是固定的，而是一组。

现在问题转换为，对于某个员工，已经知道前 $i - 1$ 个下属可以获得的最大收益 $g_{i-1}(b,k)$ ，对第 $i$ 个员工，应该消耗多少费用才能使得 $g_i(b,k)$ 最大，而这是一个贪心问题：

$g_i(b,k)=\operatorname* {max}_{0\le b_v\le b} g_{i-1}(b-b_v,k)+f_{v_i}(b_v,k)$

在算到所有的 $g (b, k)$ 后，我们就知道了给所有下属b费用可以得到的最大收益，此时状态转移变成了：

$f_u(b,k)= max\{g_v(b,0), g(b-c_k, 1)+p_k\}$

最后的问题在大的框架上是一个树型DP，每个节点上叶子到节点的状态转移是一个0-1背包问题，在这个0-1背包问题每个物体的选择上又是一个贪心问题。

经过一段时间的理解我才梳理出整个思路，最后的代码实现使用了0-1背包的滚动数组优化。自己的思维深度还是不够，同时也应该梳理思考的顺序，把已知、转换过程都用纸笔记录下来，可以帮助自己固定思维的结果，否则想着想着都糊涂了，人类的能力真是有局限的啊（迪奥笑）。

D. 3563. 移除相邻字符后字典序最小的字符串

AC代码

class Solution {static bool is_pair(char a, char b) {int diff = abs(a - b);return diff == 1 || diff == 25;}
public:string lexicographicallySmallestString(string s) {int n = s.size();vector dp2(n, vector<int>(n, 1));for (int i = 0; i < n; ++i) dp2[i][i] = 0;for (int l = 2; l <= n; ++l) {for (int i = 0; i + l - 1 < n; ++i) {int j = i + l - 1;dp2[i][j] = 0;if (is_pair(s[i], s[j])) {dp2[i][j] = dp2[i + 1][j - 1];if (dp2[i][j]) {continue;}}for (int k = i + 1; k < j; ++k) {dp2[i][j] = (dp2[i][k] && dp2[k + 1][j]);if (dp2[i][j]) {break;}}}}vector<string> dp(n + 1);for (int i = n - 1; i >= 0; --i) {auto &&ans = dp[i];ans.push_back(s[i]);ans.append(dp[i + 1]);for (int j = i + 1; j < n; ++j) {if (dp2[i][j]) {ans = min(ans, dp[j + 1]);}}}return dp[0];}
};

思路分析

比赛的时候没有看清楚题目，想当然的以为和第二题一样是从最左边删除，然后写了一通模拟，结果理所当然地过不了。在任意位置删除相邻对的情况下，显然已经不能模拟，只能考虑动态规划或者贪心。

由于求的是最小的串，所以有最优子结构。可是前面的删除似乎会影响后面的删除，这样看来是有后效性的，似乎看起来应该去思考贪心，但是贪心也没有很好的想法，起决定作用的是前面的字符，但前面的字符有可能是通过后面的字符会删除掉。

听了灵神的讲解后发现还是要沉下心去思考。我们上面觉得前面的字符可能和后面的字符配对删除所以有后效性，但是如果确定删除了就没有后效性了。尝试定义状态dp[i]为i开始的字符串删除配对后可以得到的最小字符串，考虑状态转移：

如果s[i]不删除，那显然dp[i] = s[i] + dp[i + 1]
关键在于s[i]如果可以删除呢，问题变成了s[i]开始多少个字符可以删掉。由于n很小，所以我们可以遍历[i, j]字符串，如果s[i, j]可以删除，dp[i]= min(dp[i], dp[j])。

现在问题转换为，如何快速判断s[i, j]是否可以删除。灵神说可以联想到合法括号字符串（RBS），使用区间DP处理。难点在于，我联想不到，注意力薄弱。

最终问题通过区间DP处理出哪些区间可以被消除，再用线性DP算出以某个字符开始可以得到的最小字符串。