【算法日记】Day 16 动态规划专题——树状DP基础（四）

张开发
• 2026/4/16 23:08:15 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法日记】Day 16 动态规划专题——树状DP基础（四）
Abstract#树状DP#DFS#贪心1. 题目题目LeetCode 2477. 到达首都的最小油耗核心思路每个节点的人都要前往根节点每辆车可坐seats人同一辆车可以多次往返。计算最小总油耗时采用贪心策略对每条边考虑其子树中的人数需要的最少车辆数为ceil(size[u] / seats)这些车辆都必须经过该边一次去根因此该边对油耗的贡献就是ceil(size[u] / seats)。后序遍历累计即可。复杂度时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)邻接表 递归栈。2. 代码constintMAXN100005;classSolution{public:structEdge{intto,next;}edges[2*MAXN];inthead[MAXN],cnt;voidadd_edge(intu,intv){edges[cnt]{v,head[u]};head[u]cnt;}longlongans0;intseats;intdfs(intu,intparent){intsize1;// 当前子树总人数包括自己for(inteihead[u];ei!-1;eiedges[ei].next){intvedges[ei].to;if(vparent)continue;intchildSizedfs(v,u);sizechildSize;// 子节点到当前节点这条边需要的车辆数ans(childSizeseats-1)/seats;}returnsize;}longlongminimumFuelCost(vectorvectorintroads,intseats){this-seatsseats;cnt0;memset(head,-1,sizeof(head));for(autoroad:roads){add_edge(road[0],road[1]);add_edge(road[1],road[0]);}dfs(0,-1);returnans;}};3. 心得贪心策略每条边的油耗 ceil(子树人数 / seats)因为车辆应尽可能坐满且每辆车必须经过该边一次。父节点参数作用传递parent防止递归回溯确保只向下遍历子树这是树上DFS的标准写法。数据类型人数可能很多n最多达10 5 10^5105油耗可能超过int范围用long long更安全。4. 相关题目LeetCode 834. 树中距离之和LeetCode 310. 最小高度树

更多文章