以下是 LeetCode 3530 有向无环图中合法拓扑排序的最大利润 的 C 实现。思路概述- 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)完整代码cppclass Solution {public:int maxProfit(int n, vectorvectorint edges, vectorint score) {int maxMask 1 n;// need[i] 节点 i 的所有前驱节点的位掩码vectorint need(n, 0);// dp[mask] 已选 mask 中节点时的最大利润vectorint dp(maxMask, -1);dp[0] 0;// 构建前驱掩码for (auto edge : edges) {int u edge[0];int v edge[1];need[v] | 1 u;}for (int mask 0; mask maxMask; mask) {if (dp[mask] -1) continue;int pos __builtin_popcount(mask) 1; // 下一个位置1-basedfor (int i 0; i n; i) {// i 不在 mask 中且 i 的所有前驱都已在 mask 中if ((mask (1 i)) 0 (need[i] mask) need[i]) {int nextMask mask | (1 i);dp[nextMask] max(dp[nextMask], dp[mask] score[i] * pos);}}}return dp[maxMask - 1];}};关键点说明1. need[i] 的构建need[v] | 1 u 表示节点 u 必须在 v 之前。转移条件 (need[i] mask) need[i] 等价于 need[i] 是 mask 的子集即 i 的所有前驱都已处理。2. 位置计算pos __builtin_popcount(mask) 1因为 mask 中已有 popcount(mask) 个节点下一个节点自然排在第 popcount 1 位。3. DP 初始化dp[0] 0其余为 -1 表示不可达。由于 score[i] ≥ 1 且 pos ≥ 1利润恒为正-1 作为不可达标记是安全的。4. 枚举顺序按 mask 从小到大枚举保证每个状态只被前面的状态更新一次。
以下是 LeetCode 3530 有向无环图中合法拓扑排序的最大利润 的 C 实现。思路概述- 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)完整代码cppclass Solution {public:int maxProfit(int n, vectorvectorint edges, vectorint score) {int maxMask 1 n;// need[i] 节点 i 的所有前驱节点的位掩码vectorint need(n, 0);// dp[mask] 已选 mask 中节点时的最大利润vectorint dp(maxMask, -1);dp[0] 0;// 构建前驱掩码for (auto edge : edges) {int u edge[0];int v edge[1];need[v] | 1 u;}for (int mask 0; mask maxMask; mask) {if (dp[mask] -1) continue;int pos __builtin_popcount(mask) 1; // 下一个位置1-basedfor (int i 0; i n; i) {// i 不在 mask 中且 i 的所有前驱都已在 mask 中if ((mask (1 i)) 0 (need[i] mask) need[i]) {int nextMask mask | (1 i);dp[nextMask] max(dp[nextMask], dp[mask] score[i] * pos);}}}return dp[maxMask - 1];}};关键点说明1. need[i] 的构建need[v] | 1 u 表示节点 u 必须在 v 之前。转移条件 (need[i] mask) need[i] 等价于 need[i] 是 mask 的子集即 i 的所有前驱都已处理。2. 位置计算pos __builtin_popcount(mask) 1因为 mask 中已有 popcount(mask) 个节点下一个节点自然排在第 popcount 1 位。3. DP 初始化dp[0] 0其余为 -1 表示不可达。由于 score[i] ≥ 1 且 pos ≥ 1利润恒为正-1 作为不可达标记是安全的。4. 枚举顺序按 mask 从小到大枚举保证每个状态只被前面的状态更新一次。
