LeetCode:2646. 最小化旅行的价格总和(dfs + 树形dp C++、Java)

目录

2646. 最小化旅行的价格总和

题目描述:

实现代码与解析:

DFS + DP

原理思路:


2646. 最小化旅行的价格总和

题目描述:

        现有一棵无向、无根的树,树中有 n 个节点,按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ,其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ,其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行,并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前,你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

示例 1:

输入:n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出:23
解释:
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树,第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行,选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行,选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行,选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明,23 是可以实现的最小答案。

示例 2:

输入:n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出:1
解释:
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树,第二个图表示选择节点 0 并使其价格减半后的树。 
第 1 次旅行,选择路径 [0] 。路径的价格总和为 1 。 
所有旅行的价格总和为 1 。可以证明,1 是可以实现的最小答案。

提示:

  • 1 <= n <= 50
  • edges.length == n - 1
  • 0 <= ai, bi <= n - 1
  • edges 表示一棵有效的树
  • price.length == n
  • price[i] 是一个偶数
  • 1 <= price[i] <= 1000
  • 1 <= trips.length <= 100
  • 0 <= starti, endi <= n - 1

实现代码与解析:

DFS + DP

C++

class Solution {
public:
    int N = 50 + 10;
    vector<int> e = vector<int>(N * 2, 0), ne = vector<int>(N * 2, 0), h = vector<int>(N, -1);
    vector<int> cnt = vector<int>(N, 0);
    int idx= 0;
    // 邻接表加边 
    void add(int a, int b) {
        e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
    }

    bool dfs(int cur, int p, int end) {
        if (cur == end) {
            cnt[cur]++;
            return true;
        }

        for (int i = h[cur]; ~i; i = ne[i]) {
            int j = e[i];
            if (j == p) continue;
            if (dfs(j, cur, end)) {
                cnt[cur]++;
                return true;
            }
        }
        return false;
    }

    // first,当前节点不减半可以获得的最小金额,second,当前节点减半
    pair<int, int> dpf(int cur, int p, vector<int> price) {
        pair<int, int> res = {price[cur] * cnt[cur], price[cur] * cnt[cur] / 2};
        for (int i = h[cur]; ~i; i = ne[i]) {
            int j = e[i];
            if (j == p) continue;
            pair<int, int> t = dpf(j, cur, price);
            res.first += min(t.first, t.second); // 当前节点不减半,那么孩子可减半,也可不减取最大
            res.second += t.first; // 当前节点减半,子节点一定不能减半
        }
        return res;
    }
    int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
        
        // 初始化图
        for (auto e: edges) {
            add(e[0], e[1]);
            add(e[1], e[0]);
        }

        // dfs
        for (auto t: trips) {
            dfs(t[0], -1, t[1]);
        }

        auto [x, y] = dpf(0, -1, price);

        return min(x, y); // 取最小

    }
};

Java

class Solution {
    public int N = 50 + 10;
    public int[] e = new int[N * 2], ne = new int[N * 2], h = new int[N];
    public int[] cnt = new int[N];
    public int idx = 0;

    public void add(int a, int b) {
        e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
    }

    public boolean dfs(int cur, int p, int end) {
        if (cur == end) {
            cnt[cur]++;
            return true;
        }
        for (int i = h[cur]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == p) continue;
            if (dfs(j, cur, end)) {
                cnt[cur]++;
                return true;
            }
        }

        return false;
    }

    public int[] dp(int cur, int p, int[] price) {
        
        int[] res = {price[cur] * cnt[cur], price[cur] * cnt[cur] / 2};
        
        for (int i = h[cur]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == p) continue;
            int[] t = dp(j, cur, price);
            res[0] += Math.min(t[0], t[1]);
            res[1] += t[0];
        }
        return res;
    }
    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        Arrays.fill(h, -1);
        
        for (int[] t: edges) {
            add(t[0], t[1]);
            add(t[1], t[0]);
        }

        for (int[] t: trips) {
            dfs(t[0], -1, t[1]);
        }

        int[] res = dp(0, -1, price);

        return Math.min(res[0], res[1]);
    }
}

原理思路:

        此题,可以拆分为两道题,DFS + 树形DP

dp之前先用dfs遍历处理一下,找出每个节点总共经过的次数。

dp返回数组的含义和递推式:

        res[0]表示,此节点不减半可获得的最小值,此节点不减半,那么其孩子节点就可减半,可不减半,取最小min。res[0] += min(childres[0], childres[1]); // 这里用childres来表示孩子返回值解释

        res[1]表示,此节点减半可获取的最小值,此节点减半,那么其孩子节点就一定不能减半,直接加上孩子返回的不减半值即可。 res[1] += childres[0];

和树形的 打家劫舍III 思路相同,只不过那题是取最大值。

Leetcode每日一题:打家劫舍系列Ⅰ、Ⅱ、Ⅲ、Ⅳ(2023.9.16~2023.9.19 C++)_Cosmoshhhyyy的博客-CSDN博客

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/223876.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

团队git操作流程

项目的开发要求&#xff1a;&#xff08;1&#xff09;项目组厉员代码提交不少于20次 &#xff08;2&#xff09;项目组厉员每天提交不少于20次 &#xff08;3&#xff09;企业项目开发代码的每天的提交一般提交3-5次 &#xff08;4&#xff09;代码仓库的管理 git的基础操作流…

案例042:基于微信小程序的居住证申报系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…

OpenCV-python numpy和基本作图

文章目录 一、实验目的二、实验内容三、实验过程Numpy1.NumPy 操作2.NumPy Ndarray 对象3.NumPy 基本类型4.NumPy 数组属性ndarray.ndimndarray.shapendarray.itemsizendarray.flags 5.NumPy 创建数组numpy.emptynumpy.zerosnumpy.ones 6.NumPy 从已有的数组创建数组numpy.asar…

【Python】Python读Excel文件生成xml文件

目录 ​前言 正文 1.Python基础学习 2.Python读取Excel表格 2.1安装xlrd模块 2.2使用介绍 2.2.1常用单元格中的数据类型 2.2.2 导入模块 2.2.3打开Excel文件读取数据 2.2.4常用函数 2.2.5代码测试 2.2.6 Python操作Excel官方网址 3.Python创建xml文件 3.1 xml语法…

HCL Domino 12系统管理员考试

大家好&#xff0c;才是真的好。 12月份的某一天&#xff0c;趁着风和日丽&#xff0c;天朗气清&#xff0c; 下了舍弃100多美金的狠心&#xff0c;在Pearson Vue官网上报了HCL Domino 12系统管理员考试的名 。时隔十五年后&#xff0c;骑着电动车风风火火地前往某一当地考试中…

AI Pika 生成进击的巨人动漫分镜案例

背景介绍 Pika 是一个使用 AI 生成和编辑视频的平台。它致力于通过 AI 技术使视频制作变得简单和无障碍。 Pika 1.0 是 Pika 的一个重大产品升级&#xff0c;包含了一个新的 AI 模型,可以在各种风格下生成和编辑视频,如 3D 动画&#xff0c;动漫&#xff0c;卡通和电影风格。…

pytorch中的transpose用法

注意&#xff1a;维数从0开始&#xff0c;0维 1维2维…,负数代表从右往左数&#xff0c;-1代表第一维&#xff0c;以此类推 import torch import numpy as np# 创建一个二维数组 arr torch.tensor([[[1, 2],[3, 4]],[[5, 6],[7, 8]]]) print("原始数组&#xff1a;"…

深入理解 Java 虚拟机(JVM)从入门到精通

目录 一、JVM内存结构1、堆&#xff08;Heap&#xff09;&#xff08;1&#xff09;特点&#xff08;2&#xff09;堆内存分配&#xff08;3&#xff09;晋升到老年代的方式&#xff08;4&#xff09;堆内存检验方式2、虚拟机栈&#xff08;VM Stack&#xff09;&#xff08;1&…

Vis.js教程(二):基础关系图实现

首先引用所需要的css和js文件 <link href"https://cdn.bootcdn.net/ajax/libs/vis-network/9.1.6/dist/dist/vis-network.min.css" rel"stylesheet"> <script src"https://cdn.bootcdn.net/ajax/libs/vis-network/9.1.6/standalone/umd/vis-…

python+requests+excel 接口测试

1、EXCEL文件接口保存方式&#xff0c;如图。 2、然后就是读取EXCEL文件中的数据方法&#xff0c;如下&#xff1a; 1 import xlrd2 3 4 class readExcel(object):5 def __init__(self, path):6 self.path path7 8 property9 def getSheet(self): 10 …

前端编码中快速填充内容--乱数假文

写前端页面的时候&#xff0c;如果要快速插入图片&#xff0c;可以使用 https://picsum.photos/ 详见笔者这篇博文&#xff1a; 工具网站&#xff1a;随机生成图片的网站-CSDN博客 可是&#xff0c;如果要快速填充文字内容该怎么做呢&#xff1f; 以前&#xff0c;我们都是…

【GAMES101】二维变换和齐次坐标

这几天都在抽空学OpenGL、敲leetcode和看games&#xff0c;这里留点笔记给以后复习 games101第一节课在吹水&#xff0c;第二节课讲了线性代数的入门知识&#xff0c;比较简单&#xff0c;这里稍微回顾一下重点&#xff0c;然后开始讲第三节课的二维变换和齐次坐标 目录 向量…

ACM32F42X系列芯片有何性能?为什么可以应用在工业控制 中等产品上

ACM32F42X 芯片的内核基于 ARMv8-M 架构&#xff0c;支持 Cortex-M33 和 Cortex-M4F 指令集。内核支持一 整套 DSP 指令用于数字信号处理&#xff0c;支持单精度 FPU 处理浮点数据&#xff0c;同时还支持 Memory Protection Unit &#xff08;MPU&#xff09;用于提升应用的安全…

C++[面向对象的程序设计]_基础入门(上)(万字总结)(建议收藏!!!)

目录 1. C基础入门 1.1 变量 1.2 常量 1.3 关键字 1.4 标识符命名规则 1.5 数据类型 1.5.1 整型 1.5.2 sizeof 关键字 1.5.3 实型&#xff08;浮点型&#xff09; 1.5.4 字符型 1.5.5 转义字符 1.5.6 字符串类型 1.5.7 布尔类型 1.5.8 数据的输入 1.6 运算符 …

ps快捷键和常见项目总结

处理以像素构成的位图的软件 Mac笔记本快捷键&#xff1a; 打开文件&#xff1a;commandO 图像缩放&#xff1a;command 多个文件切换&#xff1a;同一桌面中&#xff1a;command (英文状态下输入) 切换屏幕模式&#xff1a;F,全屏模式下Tab键可进行切换 首选项—性能&a…

python/matlab图像去雾/去雨综述

图像去雾和去雨是计算机视觉领域的两个重要任务&#xff0c;旨在提高图像质量和可视化效果。本文将综述图像去雾和去雨的算法、理论以及相关项目代码示例。 一、图像去雾算法 基于暗通道先验的方法&#xff1a; 这是广泛应用于图像去雾的经典算法之一。该方法基于一个观察&…

SpringMVC修炼之旅(2)基础入门

一、第一个程序 1.1环境配置 略 1.2代码实现 package com.itheima.controller;import org.springframework.stereotype.Controller; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.ResponseBody;//定义…

MySQL联合查询、最左匹配、范围查询导致失效

服务器版本 客户端&#xff1a;navicat premium16.0.11 联合索引 假设有如下表 联合索引就是同时把多列设成索引&#xff0c;如(empno&#xff0c;ename)在查询的时候就会先按照empno进行查询&#xff0c;再按照ename进行查询其中empno是全局有序&#xff0c;ename是局部有…

【银行测试】支付类测试关注点与异常点+支付平台...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、支付类的测试关…

Django回顾 - 6 Ajax

【1】Ajax 定义&#xff1a; 异步Javscript和XML 作用&#xff1a; Javascript语言与服务器(django)进行异步交互&#xff0c;传输的数据为XML&#xff08;当然&#xff0c;传输的数据不只是XML,现在更多使用json数据&#xff09; 同步交互和异步交互&#xff1a; 1、同步交互&…