第 451 场周赛-20250525
https://leetcode.cn/contest/weekly-contest-451/
中国时间：2025-05-25 10:30, 1 小时 30 分
E3560.木材运输的最小成本
implementation, https://leetcode.cn/problems/find-minimum-log-transportation-cost/description/
M3561.移除相邻字符
stack, https://leetcode.cn/problems/resulting-string-after-adjacent-removals/
T3562.折扣价交易股票的最大利润
树形DP + 多重背包合并, https://leetcode.cn/problems/maximum-profit-from-trading-stocks-with-discounts/
给你一个整数 n，表示公司中员工的数量。每位员工都分配了一个从 1 到 n 的唯一 ID ，其中员工 1 是 CEO。另给你两个下标从 1 开始的整数数组 present 和 future，两个数组的长度均为 n，具体定义如下：
present[i]表示第i位员工今天可以购买股票的 当前价格 。future[i]表示第i位员工明天可以卖出股票的 预期价格 。
公司的层级关系由二维整数数组 hierarchy 表示，其中 hierarchy[i] = [ui, vi] 表示员工 ui 是员工 vi 的直属上司。
此外，再给你一个整数 budget，表示可用于投资的总预算。
公司有一项折扣政策：如果某位员工的直属上司购买了自己的股票，那么该员工可以以 半价 购买自己的股票（即 floor(present[v] / 2)）。
请返回在不超过给定预算的情况下可以获得的 最大利润 。
注意：
- 每只股票最多只能购买一次。
- 不能使用股票未来的收益来增加投资预算，购买只能依赖于
budget。
示例 1：
输入： n = 2, present = [1,2], future = [4,3], hierarchy = [[1,2]], budget = 3
输出： 5
解释：
- 员工 1 以价格 1 购买股票，获得利润
4 - 1 = 3。 - 由于员工 1 是员工 2 的直属上司，员工 2 可以以折扣价
floor(2 / 2) = 1购买股票。 - 员工 2 以价格 1 购买股票，获得利润
3 - 1 = 2。 - 总购买成本为
1 + 1 = 2 <= budget，因此最大总利润为3 + 2 = 5。
示例 2：
输入： n = 2, present = [3,4], future = [5,8], hierarchy = [[1,2]], budget = 4
输出： 4
解释：
- 员工 2 以价格 4 购买股票，获得利润
8 - 4 = 4。 - 由于两位员工无法同时购买，最大利润为 4。
示例 3：
输入： n = 3, present = [4,6,8], future = [7,9,11], hierarchy = [[1,2],[1,3]], budget = 10
输出： 10
解释：
- 员工 1 以价格 4 购买股票，获得利润
7 - 4 = 3。 - 员工 3 可获得折扣价
floor(8 / 2) = 4，获得利润11 - 4 = 7。 - 员工 1 和员工 3 的总购买成本为
4 + 4 = 8 <= budget，因此最大总利润为3 + 7 = 10。
示例 4：
输入： n = 3, present = [5,2,3], future = [8,5,6], hierarchy = [[1,2],[2,3]], budget = 7
输出： 12
解释：
- 员工 1 以价格 5 购买股票，获得利润
8 - 5 = 3。 - 员工 2 可获得折扣价
floor(2 / 2) = 1，获得利润5 - 1 = 4。 - 员工 3 可获得折扣价
floor(3 / 2) = 1，获得利润6 - 1 = 5。 - 总成本为
5 + 1 + 1 = 7 <= budget，因此最大总利润为3 + 4 + 5 = 12。
提示：
1 <= n <= 160present.length, future.length == n1 <= present[i], future[i] <= 50hierarchy.length == n - 1hierarchy[i] == [ui, vi]1 <= ui, vi <= nui != vi1 <= budget <= 160- 没有重复的边。
- 员工 1 是所有员工的直接或间接上司。
- 输入的图
hierarchy保证 无环 。
下面给出基于「树形动态规划 + 多重背包合并」的 O(n⋅budget2) 解法。核心思路是对以 1 号员工为根的管理树做 DFS，对于每个节点在「父亲是否买入自己」两种情形下分别计算一个长度为 budget+1 的 DP 数组，最后答案取根节点父情形为“不打折”时的最优值。
from typing import List
import sys
sys.setrecursionlimit(10000)
class Solution:
def maxProfit(self, n: int, present: List[int], future: List[int], hierarchy: List[List[int]], budget: int) -> int:
# Build the tree
children = [[] for _ in range(n)]
for u, v in hierarchy:
# Convert to 0-based index
children[u - 1].append(v - 1)
# DFS 返回 dp[p][c]:
# p ∈ {0,1} 表示「当前节点的上司是否买了自己」，
# dp[p] 是长度为 budget+1 的数组，dp[p][c] = 在预算恰好使用 c 时的最大总利润
def dfs(u: int) -> List[List[int]]:
# 先对子节点做 dfs
child_dp = [dfs(v) for v in children[u]]
# 为两种父亲购买情形各自做一次子树合并
dp = [[-10 ** 18] * (budget + 1) for _ in range(2)]
for parent_bought in (0, 1):
# 考虑「不买自己」和「买自己」两种选择
# buy=0: cost=0, profit=0, children see parent_bought_child=0
# buy=1: cost按情况，profit=future-present_cost, children see parent_bought_child=1
# 我们先对这两种情况分别做子节点的背包合并，然后再在最后按成本选最优
# tmp_dp[k] 表示当前已合并到某一步，恰耗费 k 时的最大利润
tmp_dp = [-10 ** 18] * (budget + 1)
# 枚举是否在 u 节点买入
for buy in (0, 1):
# 计算买入自己的成本和直接利润
if buy == 0:
cost_u, profit_u, child_flag = 0, 0, 0
else:
# 折扣价
price = present[u] if parent_bought == 0 else (present[u] // 2)
cost_u, profit_u, child_flag = price, future[u] - price, 1
# —— 去掉下面这行 ——
# if profit_u < 0: continue
# 如果单独买入超预算，跳过
if cost_u > budget:
continue
# 初始化 cur_dp
cur_dp = [-10 ** 18] * (budget + 1)
cur_dp[cost_u] = profit_u
# 依次将每个子树进行「背包卷积」
for cdp in child_dp:
nxt_dp = [-10 ** 18] * (budget + 1)
# cdp[child_flag] 数组是子节点在 parent_bought=child_flag 下的 dp
child_flag_dp = cdp[child_flag]
# 在剩余预算里，子树可选任意开销
for used in range(budget + 1):
if cur_dp[used] < -10 ** 17:
continue
for spend in range(budget - used + 1):
if child_flag_dp[spend] < -10 ** 17:
continue
val = cur_dp[used] + child_flag_dp[spend]
if val > nxt_dp[used + spend]:
nxt_dp[used + spend] = val
cur_dp = nxt_dp
# 将 cur_dp 合并进 tmp_dp
for c in range(budget + 1):
if cur_dp[c] > tmp_dp[c]:
tmp_dp[c] = cur_dp[c]
dp[parent_bought] = tmp_dp
return dp
# 根节点（编号0）上司一定没有给它打折 => 用 parent_bought=0 的 dp
root_dp = dfs(0)[0]
# 预算不限于恰好，允许 ≤ budget，所以要再多一次「前缀最大」
return max(root_dp[:budget + 1])
if __name__ == "__main__":
sol = Solution()
print(sol.maxProfit(2, [6, 11], [5, 48], [[1, 2]], 142)) # 42复杂度分析：
- 每个节点有两种「父亲是否买过自己」情形；
- 对每种情形做两种「自己买／不买」选择；
- 并将子树的背包状态与当前状态做 O(budget2) 的卷积；
- 整体时间 O(n×budget2)，在 n, budget≤160 时完全可行。
在「剪掉亏本交易」的第42行代码。由于给上级“牺牲小利”也可能给下属带来更大利，不能简单地 if profit_u < 0: continue。我们把那行去掉，就能在必要时允许父节点“先亏后赚”。
T3563.移除相邻字符后字典序最小的字符串
https://leetcode.cn/problems/lexicographically-smallest-string-after-adjacent-removals/
给你一个由小写英文字母组成的字符串 s。
你可以进行以下操作任意次（包括零次）：
- 移除字符串中 任意 一对 相邻 字符，这两个字符在字母表中是 连续 的，无论顺序如何（例如，
'a'和'b'，或者'b'和'a'）。 - 将剩余字符左移以填补空隙。
返回经过最优操作后可以获得的 字典序最小 的字符串。
当且仅当在第一个不同的位置上，字符串 a 的字母在字母表中出现的位置早于字符串 b 的字母，则认为字符串 a 的 字典序小于 字符串 b，。 如果 min(a.length, b.length) 个字符都相同，则较短的字符串字典序更小。
注意：字母表被视为循环的，因此 'a' 和 'z' 也视为连续。
示例 1：
输入： s = "abc"
输出： "a"
解释：
- 从字符串中移除
"bc"，剩下"a"。 - 无法进行更多操作。因此，经过所有可能的移除后，字典序最小的字符串是
"a"。
示例 2：
输入： s = "bcda"
输出： ""
解释：
- 从字符串中移除
"cd"，剩下"ba"。 - 从字符串中移除
"ba"，剩下""。 - 无法进行更多操作。因此，经过所有可能的移除后，字典序最小的字符串是
""。
示例 3：
输入： s = "zdce"
输出： "zdce"
解释：
- 从字符串中移除
"dc"，剩下"ze"。 - 无法对
"ze"进行更多操作。 - 然而，由于
"zdce"的字典序小于"ze"。因此，经过所有可能的移除后，字典序最小的字符串是"zdce"。
提示：
1 <= s.length <= 250s仅由小写英文字母组成。
class Solution:
def lexicographicallySmallestString(self, s: str) -> str: