以下是 LeetCode 3530 有向无环图中合法拓扑排序的最大利润 的 Rust 实现。思路概述- n ≤ 22使用状压 DPBitmask DP。- need[i]节点 i 的所有直接前驱的位掩码。- dp[mask]已经选了 mask 中这些节点能获得的最大利润。- 转移时已选节点数为 popcount(mask)下一个位置为 pos bitCount 1。枚举所有不在 mask 中且所有前驱都已选的节点 i更新 dp[mask | (1i)]。- 最终答案为 dp[(1n) - 1]。复杂度- 时间O(2^n · n)由于 n ≤ 22约为 2200 万级别。- 空间O(2^n)完整代码rustimpl Solution {pub fn max_profit(n: i32, edges: VecVeci32, score: Veci32) - i32 {let n n as usize;let max_mask 1 n;// need[i] 节点 i 的所有前驱节点的位掩码let mut need vec![0; n];// dp[mask] 已选 mask 中节点时的最大利润let mut dp vec![-1; max_mask];dp[0] 0;// 构建前驱掩码for edge in edges {let u edge[0] as usize;let v edge[1] as usize;need[v] | 1 u;}for mask in 0..max_mask {if dp[mask] -1 {continue;}let pos (mask.count_ones() 1) as i32; // 下一个位置1-basedfor i in 0..n {// i 不在 mask 中且 i 的所有前驱都已在 mask 中if (mask (1 i)) 0 (need[i] mask) need[i] {let next_mask mask | (1 i);dp[next_mask] dp[next_mask].max(dp[mask] score[i] * pos);}}}dp[max_mask - 1]}}关键点说明1. need[i] 的构建need[v] | 1 u 表示节点 u 必须在 v 之前。转移条件 (need[i] mask) need[i] 等价于 need[i] 是 mask 的子集即 i 的所有前驱都已处理。2. 位置计算pos mask.count_ones() 1因为 mask 中已有 count_ones() 个节点下一个节点自然排在第 count_ones() 1 位。3. DP 初始化dp[0] 0其余为 -1 表示不可达。由于 score[i] ≥ 1 且 pos ≥ 1利润恒为正-1 作为不可达标记是安全的。4. 枚举顺序按 mask 从小到大枚举保证每个状态只被前面的状态更新一次。
以下是 LeetCode 3530 有向无环图中合法拓扑排序的最大利润 的 Rust 实现。思路概述- n ≤ 22使用状压 DPBitmask DP。- need[i]节点 i 的所有直接前驱的位掩码。- dp[mask]已经选了 mask 中这些节点能获得的最大利润。- 转移时已选节点数为 popcount(mask)下一个位置为 pos bitCount 1。枚举所有不在 mask 中且所有前驱都已选的节点 i更新 dp[mask | (1i)]。- 最终答案为 dp[(1n) - 1]。复杂度- 时间O(2^n · n)由于 n ≤ 22约为 2200 万级别。- 空间O(2^n)完整代码rustimpl Solution {pub fn max_profit(n: i32, edges: VecVeci32, score: Veci32) - i32 {let n n as usize;let max_mask 1 n;// need[i] 节点 i 的所有前驱节点的位掩码let mut need vec![0; n];// dp[mask] 已选 mask 中节点时的最大利润let mut dp vec![-1; max_mask];dp[0] 0;// 构建前驱掩码for edge in edges {let u edge[0] as usize;let v edge[1] as usize;need[v] | 1 u;}for mask in 0..max_mask {if dp[mask] -1 {continue;}let pos (mask.count_ones() 1) as i32; // 下一个位置1-basedfor i in 0..n {// i 不在 mask 中且 i 的所有前驱都已在 mask 中if (mask (1 i)) 0 (need[i] mask) need[i] {let next_mask mask | (1 i);dp[next_mask] dp[next_mask].max(dp[mask] score[i] * pos);}}}dp[max_mask - 1]}}关键点说明1. need[i] 的构建need[v] | 1 u 表示节点 u 必须在 v 之前。转移条件 (need[i] mask) need[i] 等价于 need[i] 是 mask 的子集即 i 的所有前驱都已处理。2. 位置计算pos mask.count_ones() 1因为 mask 中已有 count_ones() 个节点下一个节点自然排在第 count_ones() 1 位。3. DP 初始化dp[0] 0其余为 -1 表示不可达。由于 score[i] ≥ 1 且 pos ≥ 1利润恒为正-1 作为不可达标记是安全的。4. 枚举顺序按 mask 从小到大枚举保证每个状态只被前面的状态更新一次。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
