当前位置: 首页 > news >正文

力扣370周赛 -- 第三题(树形DP)

该题的方法,也有点背包的意思,如果一些不懂的朋友,可以从背包的角度去理解该树形DP

问题

题解主要在注释里

         //该题是背包问题+树形dp问题的结合版,在树上解决背包问题

         //背包问题就是选或不选当前物品

         //本题求的是最大分数

         //先转成背包问题理解

         //从n个物品当中选出最大分数

         //再转成有限制版的

         //从n个物品当中选出最大分数,并且血量是健康的

         //再转成树形DP去理解该问题

         

         //树是健康就是,在任意一条树的路径下(到叶子节点的任意一条路径),能确保至少有一个物品不被选

         //从树上前n个物品当中选出一些物品,并且保证树是健康的

         //从树上前i个物品当中选出保证树是健康的前提下,能选出的不超过i个物品的最大分数

         //然后再去拓展这个定义

         

         //结合树形DP的经验

         //以当前u为根节点的子树,在保证树是健康的前提下,能选出的最大分数

         //那么就有了推导过程,从下往上推导,也就是从最小子树往上推导到最大子树最大分数

         //那么最好的做法就是利用递归的特性,回溯的时候进行推导

         //这题中我们直接找出最大分数,其实是比较难的,我们用初中的思想

         //正难则反,既然找最大分数(有个不选的)比较难,那么我们可以用

         //找个最小分数(选上的),那么就变得比较简单了

         

         //状态定义

         //首先我们找最小的,以树形dp为经验推导出

         //我们以u为根节点的子树,总和最小的分数(并且是保证健康的,在一条路径上最少也得选一个)

         //定义为min_val[u]

               

         //那么怎么算出最大分数呢,既然有min_val[u],那么就有,以当前u为根节点的子树节点总和sum_val[u]

         //那么相减sum_val[u] - min_val[u]就等于最大分数了

         

         //那么如何推导这两个定义的数组呢?

         //树形dp类型问题,最好首先用dfs,边回溯边推导数组

 

class Solution {
public:void dfs_sum_val(int u,int fa,vector<int>& val,vector<vector<int>>& g,vector<long long>& sum_val){sum_val[u] = val[u];for(auto e:g[u])if(fa != e)//不要往上计算,我们是从下往上推导{dfs_sum_val(e,u,val,g,sum_val);//回溯计算sum_val[u] += sum_val[e];}//这个dfs我们可以算作一个小题,就是计算出每个点为根节点的子树的总和}void dfs_min_val(int u,int fa,vector<int>& val,vector<vector<int>>& g,vector<long long>& min_val){long long min_res = 0;min_val[u] = (long long)val[u];for(auto& e:g[u]){if(fa != e){dfs_min_val(e,u,val,g,min_val);min_res += min_val[e];}}if(min_res) min_val[u] = min((long long)min_val[u],min_res);}long long maximumScoreAfterOperations(vector<vector<int>>& edges, vector<int>& values) {//该题是背包问题+树形dp问题的结合版,在树上解决背包问题//背包问题就是选或不选当前物品//本题求的是最大分数//先转成背包问题理解//从n个物品当中选出最大分数//再转成有限制版的//从n个物品当中选出最大分数,并且血量是健康的//再转成树形DP去理解该问题//树是健康就是,在任意一条树的路径下(到叶子节点的任意一条路径),能确保至少有一个物品不被选//从树上前n个物品当中选出一些物品,并且保证树是健康的//从树上前i个物品当中选出保证树是健康的前提下,能选出的不超过i个物品的最大分数//然后再去拓展这个定义//结合树形DP的经验//以当前u为根节点的子树,在保证树是健康的前提下,能选出的最大分数//那么就有了推导过程,从下往上推导,也就是从最小子树往上推导到最大子树最大分数//那么最好的做法就是利用递归的特性,回溯的时候进行推导//这题中我们直接找出最大分数,其实是比较难的,我们用初中的思想//正难则反,既然找最大分数(有个不选的)比较难,那么我们可以用//找个最小分数(选上的),那么就变得比较简单了//状态定义//首先我们找最小的,以树形dp为经验推导出//我们以u为根节点的子树,总和最小的分数(并且是保证健康的,在一条路径上最少也得选一个)//定义为min_val[u]//那么怎么算出最大分数呢,既然有min_val[u],那么就有,以当前u为根节点的子树节点总和sum_val[u]//那么相减sum_val[u] - min_val[u]就等于最大分数了//那么如何推导这两个定义的数组呢?//树形dp类型问题,最好首先用dfs,边回溯边推导数组int edge_size = edges.size();vector<vector<int>> g(values.size() + 110);for(int i = 0;i < edge_size;i++){int a = edges[i][0];int b = edges[i][1];g[a].push_back(b);g[b].push_back(a);}vector<long long> sum_val(21000);vector<long long> min_val(21000,0x3f3f3f3f);//预处理出来sum_val数组dfs_sum_val(0,-1,values,g,sum_val);//预处理出来min_val数组dfs_min_val(0,-1,values,g,min_val);return sum_val[0] - min_val[0];}
};

相关文章:

力扣370周赛 -- 第三题(树形DP)

该题的方法&#xff0c;也有点背包的意思&#xff0c;如果一些不懂的朋友&#xff0c;可以从背包的角度去理解该树形DP 问题 题解主要在注释里 //该题是背包问题树形dp问题的结合版&#xff0c;在树上解决背包问题 //背包问题就是选或不选当前物品 //本题求的是最大分数 //先转…...

GPT学习笔记

百度的文心一言 阿里的通义千问 通过GPT能力&#xff0c;提升用户体验和产品力 GPT的出现是AI的iPhone时刻。2007年1月9日&#xff0c;第一代iPhone发布&#xff0c;开启移动互联网时代。新一轮的产业革命。 GPT模型发展时间线&#xff1a; Copilot - 副驾驶 应用&#xf…...

Apex的addError()显示的消息中实现换行

直接用‘<br/>’是无效的&#xff0c;因为addError默认不转义HTML符号&#xff0c;如果需要转义&#xff0c;应该将第二个参数escape设置为false。不过即使设置了也只对classic页面生效&#xff0c;lightning页面还是无法转义。 官方文档&#xff1a; 参考资料&#xf…...

STM32中微秒延时的实现方式

STM32中微秒延时的实现方式 0.前言一、裸机实现方式二、FreeRTOS实现方式三、定时器实现&#xff08;通用&#xff09;4、总结 0.前言 最近在STM32驱动移植过程中需要用到微秒延时来实现一些外设的时序&#xff0c;由于网上找到的驱动方法良莠不齐&#xff0c;笔者在实现时序过…...

2005-2021年全国各省家庭承包耕地面积和家庭承包耕地流转总面积数据(无缺失)

2005-2021年全国各省家庭承包耕地面积和家庭承包耕地流转总面积数据 1、时间&#xff1a;2005-2021年 2、来源&#xff1a;农村经营管理统计NB 3、指标&#xff1a;家庭承包经营耕地面积、家庭承包耕地流转总面积&#xff08;单位&#xff1a;亩&#xff09; 4、范围&#…...

【六、http】go的http的客户端重定向

一、http的重定向 重定向过程&#xff1a;客户浏览器发送http请求----》web服务器接受后发送302状态码响应及对应新的location给客户浏览器–》客户浏览器发现是302响应&#xff0c;则自动再发送一个新的http请求&#xff0c;请求url是新的location地址----》服务器根据此请求寻…...

AI:61-基于深度学习的草莓病害识别

🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌在这个漫长的过程,中途遇到了不少问题,但是…...

idea文件比对

idea文件比对 1.项目内的文件比对2.项目间的文件比对3. 剪切板对比4. 版本历史(不同分支和不同commit)对比 1.项目内的文件比对 在项目中选择好需要比对的文件(类)&#xff0c;然后选择Compare Files Mac下的快捷键是Commandd&#xff0c; 这样的比对像是git冲突解决一样 …...

重磅发布|美创科技新一代 数据安全管理平台(DSM Cloud)全新升级

重磅发布 新一代 数据安全管理平台&#xff08;DSM Cloud&#xff09; 美创科技新一代 数据安全管理平台&#xff08;简称&#xff1a;DSM Cloud&#xff09;全新升级&#xff0c;正式发布。 在业务上云飞速发展过程中&#xff0c;快速应对数据激增&#xff0c;同时有效保障数…...

比SAM小60倍的分割一切模型:MobileSAM

1 MobileSAM SAM就是一类处理图像分割任务的通用模型。与以往只能处理某种特定类型图片的图像分割模型不同&#xff0c;SAM可以处理所有类型的图像。 在SAM出现前&#xff0c;基本上所有的图像分割模型都是专有模型。比如&#xff0c;在医学领域&#xff0c;有专门分割核磁图…...

版本控制系统-SVN

SVN Apache Subversion 通常被缩写成 SVN&#xff0c;是一个开放源代码的版本控制系统。 官网&#xff1a;https://subversion.apache.org 资料&#xff1a;https://svnbook.red-bean.com、https://www.runoob.com/svn/svn-tutorial.html 下载&#xff1a;https://sourceforg…...

【电路笔记】-串联RLC电路分析

串联RLC电路分析 文章目录 串联RLC电路分析1、概述2、瞬态响应3、AC响应4、RCL和CLR配置5、结论 电阻器 、电感器 (L) 和电容器 © 是电子器件中的三个基本无源元件。 它们的属性和行为已在交流电阻、交流电感和交流电容文章中详细介绍。 在本文中&#xff0c;我们将重点讨…...

大数据毕业设计选题推荐-家具公司运营数据分析平台-Hadoop-Spark-Hive

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...

【触想智能】工业显示器上市前的检测项目分享

工业显示器在上市前&#xff0c;需要做一项重要的工作&#xff0c;那就是工业显示器出厂前的产品可靠性检测。 工业显示器选择的测试项目相比商用端更为严格&#xff0c;常见的性能测试项目包括高温老化、防尘防水、电磁静电干扰、防摔防撞等&#xff0c;在工业级应用领域&…...

Vue使用epubjs电子书

npmjs: https://www.npmjs.com/package/epubjs 在线电子书转换器 安装&#xff1a; npm i epubjs 简单封装&#xff1a; src/hooks/ import Epub from "epubjs"; import type { Book, Rendition } from epubjs import type { BookOptions } from epubjs/types…...

python机器学习——决策树

决策树 # 模块导入 from sklearn.tree import ExtraTreeRegressor as ETR, DecisionTreeRegressor as DTRExtraTreeRegressor和DecisionTreeRegressor是scikit-learn库中的两种回归模型&#xff0c;用于拟合和预测连续型目标变量。 决策树是一种基于树结构的机器学习算法&…...

__attribute__((__used__)) 和 __attribute__((__section__(“*“ “*“)))的使用

见&#xff1a;haproxy代码 C语言注册函数和调用函数&#xff0c;便于模块化开发和编程。 #include <stdio.h>#ifdef __APPLE__ #define HA_SECTION(s) __attribute__((__section__("__DATA, " s))) #define HA_SECTION_START(s) __asm("…...

webgoat-(A1)SQL Injection

SQL Injection (intro) SQL 命令主要分为三类&#xff1a; 数据操作语言 &#xff08;DML&#xff09;DML 语句可用于请求记录 &#xff08;SELECT&#xff09;、添加记录 &#xff08;INSERT&#xff09;、删除记录 &#xff08;DELETE&#xff09; 和修改现有记录 &#xff…...

Flink的API分层、架构与组件原理、并行度、任务执行计划

Flink的API分层 Apache Flink的API分为四个层次&#xff0c;每个层次都提供不同的抽象和功能&#xff0c;以满足不同场景下的数据处理需求。下面是这四个层次的具体介绍&#xff1a; CEP API&#xff1a;Flink API 最底层的抽象为有状态实时流处理。其抽象实现是Process Functi…...

Transformer:开源机器学习项目,上千种预训练模型 | 开源日报 No.66

huggingface/transformers Stars: 113.5k License: Apache-2.0 这个项目是一个名为 Transformers 的开源机器学习项目&#xff0c;它提供了数千种预训练模型&#xff0c;用于在文本、视觉和音频等不同领域执行任务。该项目主要功能包括&#xff1a; 文本处理&#xff1a;支持…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

什么是VR全景技术

VR全景技术&#xff0c;全称为虚拟现实全景技术&#xff0c;是通过计算机图像模拟生成三维空间中的虚拟世界&#xff0c;使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验&#xff0c;结合图文、3D、音视频等多媒体元素…...