备战蓝桥杯---树形DP基础3
上一次我们讲了二叉苹果树,现在我们加一点难度,从二叉变成了多叉苹果树。
这样子我们就不可以直接按照上次的方法DP,我们其实可以发现,我们可以用类似背包的思想求解,这就是所谓的树上背包。
我们先加进第一个儿子来跟新1--m的解,然后再让第二个进来更新,这样子就求出来了。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,q,x,y,head[200],v[200],cnt,z,dp[110][110];
struct node{int dian,next,quan;
}edge[210];
void merge(int x,int y,int z){edge[++cnt].dian=y;edge[cnt].quan=z;edge[cnt].next=head[x];head[x]=cnt;
}
void dfsquan(int root,int fa){for(int i=head[root];i!=-1;i=edge[i].next){if(edge[i].dian==fa) continue;v[edge[i].dian]=edge[i].quan;dfsquan(edge[i].dian,root);}return;
}
void dfsdp(int root,int fa){for(int j=q+1;j>=1;j--){dp[root][j]=v[root];}dp[root][0]=0;for(int i=head[root];i!=-1;i=edge[i].next){if(fa==edge[i].dian) continue;int ckck=edge[i].dian;dfsdp(ckck,root);for(int j=q+1;j>=1;j--){for(int k=0;k<=j-1;k++){dp[root][j]=max(dp[ckck][k]+dp[root][j-k],dp[root][j]);}}}
}
int main(){cin>>n>>q;memset(head,-1,sizeof(head));for(int i=1;i<=n-1;i++){cin>>x>>y>>z;merge(x,y,z);merge(y,x,z);}dfsquan(1,-1);dfsdp(1,-1);cout<<dp[1][q+1];
}
这里有两点注意:
1.v[root]操作不应该放在循环里面,否则会重复操作(若为边权可以)
2.转移方程中应为dp[root][j-k]而不是dp[root][j-k-1],因为root时已经把root点算进去了,不用为root留空间。
接题:

其实我们可以不用DP:
我们可以先选任意一点DFS求出权值最大的子链,我们可以证明权值最大的子链的端点之一一定是这个DFS后的端点。
下面进行证明:

我们再来看看树形DP的解法:
我们令f[i]表示以i为根的子树的最大子链,有两种情况,1.它经过i 2.他没有经过
对于经过i,我们只要把以i为起点DFS的最大长度与第二大长度相加即可。
这里我们可以简化一下:
我们令ans为答案值,dp[i]为以i为起点的最大权值,我们在求dp[i]的同时维护ans即可。
其中相加操作dp[i]记录了到目前为止的最大值(有点类似背包),通过dp[i]+dp[v]就实现了最大值与次大值相加的操作,最后维护一下dp[i]即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node1{int dian,next;
}edge[200010];
int head[100010],n,a[100010],cnt,u,v,dp[100010],ans=-10000000;
void merge(int x,int y){edge[++cnt].dian=y;edge[cnt].next=head[x];head[x]=cnt;
}
void dfsdp(int root,int fa){dp[root]=a[root];ans=max(ans,a[root]);for(int i=head[root];i!=-1;i=edge[i].next){if(edge[i].dian==fa) continue;dfsdp(edge[i].dian,root);ans=max(ans,dp[edge[i].dian]);ans=max(ans,dp[root]+dp[edge[i].dian]);dp[root]=max(dp[root],a[root]+dp[edge[i].dian]);}return;
}
signed main(){cin>>n;memset(head,-1,sizeof(head));for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}for(int i=1;i<=n-1;i++){scanf("%lld%lld",&u,&v);merge(u,v);merge(v,u);}dfsdp(1,-1);cout<<ans;
}
相关文章:
备战蓝桥杯---树形DP基础3
上一次我们讲了二叉苹果树,现在我们加一点难度,从二叉变成了多叉苹果树。 这样子我们就不可以直接按照上次的方法DP,我们其实可以发现,我们可以用类似背包的思想求解,这就是所谓的树上背包。 我们先加进第一个儿子来…...
IEEE Transactions on Industrial Electronics工业电子TIE修改稿注意事项及提交须知
一、背景 兔年末投了一篇TIE,手稿初次提交的注意事项也整理成了博客IEEE Transactions on Industrial Electronics工业电子TIE论文投稿须知,获得了许多点赞和收藏。最近也收到了审稿结果,给的意见是大修major revision,总之只要不…...
c#委托的三种实现方式
委托是实质一个类,主要目的是将方法当作参数进行传递。 委托是.NET编程的精髓之一,在日常编程中经常用到,在C#中实现委托主要有Func、Action、delegate三种方式,本节主要就这三种委托的用法通过实例展开讲解。 Func用法解析 【F…...
c/c++|红黑树|分析应用|锚点
红黑树是一种自平衡的二叉查找树,它保持着良好的平衡,能够在插入和删除等操作后通过一系列旋转和重新着色操作来保持树的平衡。这种平衡性质使得红黑树在搜索、插入和删除等操作的平均和最坏情况下的时间复杂度都是O(log n)。以下是红黑树的一些关键特性…...
2-29算法习题总结
贪心问题 小A的糖果 题目描述 小 A 有 n n n 个糖果盒,第 i i i 个盒中有 a i a_i ai 颗糖果。 小 A 每次可以从其中一盒糖果中吃掉一颗,他想知道,要让任意两个相邻的盒子中糖的个数之和都不大于 x x x,至少得吃掉几颗糖…...
当Linux 磁盘满了,查看大文件并删除
当你的Linux磁盘空间满了时,可以通过以下步骤查找大文件并删除它们: 检查磁盘空间: 使用以下命令检查磁盘空间的使用情况: df -h这将显示文件系统的使用情况,包括每个文件系统的总大小、已用空间、可用空间和挂载点。 …...
STL -萃取特性迭代器
1. STL简单概述 a. STL六大组成部分 容器(Container)空间配置器(allocator)算法(Algorithm)迭代器(Iterator)仿函数(Function object)适配器(Ad…...
python pandas写入csv
在Python的Pandas库中,可以使用to_csv方法将DataFrame对象写入CSV文件。以下是一个简单的示例: import pandas as pd# 创建一个DataFrame对象 data {Name: [Alice, Bob, Charlie, David],Age: [25, 30, 35, 40],City: [New York, Los Angeles, Chicago…...
oracle 数据库建集群式数据库的DBLINK的语法
根据需要修改以下红色字体的部分即可。 1、连接集群式数据库DBLINK语法 create public database link 自定义的dblink名字 connect to 连接对方数据库的用户名 identified by "密码" using (DESCRIPTION (ADDRESS_LIST (FAILOVER ON) (LOAD_BALANCE OFF) …...
基于JAVA的毕业设计分配选题系统 开源项目
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 专业档案模块2.2 学生选题模块2.3 教师放题模块2.4 选题审核模块 三、系统展示四、核心代码4.1 查询专业4.2 新增专业4.3 选择课题4.4 取消选择课题4.5 审核课题 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpri…...
Android 接入指纹识别
接入指纹框架:https://github.com/Tencent/soter implementation com.github.Tencent.soter:soter-wrapper:2.0.91.Application中初始化 class IApplication : Application() {override fun onCreate() {super.onCreate()instance thisinitSort()}private fun in…...
如何通过代理IP安全使用Linkedln领英?
LinkedIn是跨境外贸必备的拓客工具,世界各地的许多专业人士都使用领英来作为发布和共享内容的主要工具,这使得它成为跨境出海必备的渠道工具。 但是不少做外贸的朋友都知道,领英账号很容易遭遇限制封禁,但如果善用工具࿰…...
嵌入式驱动学习第一周——定时器与延时函数
前言 这篇博客一起学习定时器,定时器是最常用到的功能之一,其最大的作用之一就是提供了延时函数。 嵌入式驱动学习专栏将详细记录博主学习驱动的详细过程,未来预计四个月将高强度更新本专栏,喜欢的可以关注本博主并订阅本专栏&…...
Tips杂记
🥲 🥸 🤌 🫀 🫁 🥷 🐻❄️🦤 🪶 🦭 🪲 🪳 🪰 🪱 🪴 🫐 🫒 🫑…...
可以用numpy为for加速
Numpy除了用于科学计算,还有一个功能是可以代替某些for循环,进行同样的功能实现,有于是向量矩阵运算,碰到复杂的for时,计算速度可以提高,从而提高程序性能。以下是一些常用的NumPy函数和操作,可…...
cartographer ceres后端优化
这里引用一篇文章 https://zhuanlan.zhihu.com/p/567635409 因为cartographer中的代码有的地方添加了AddParameterBlock,有的地方没有添加,会引起歧义,原来AddParameterBlock可以隐式添加优化变量,这篇文章介绍了具体原因,核心内容如下: AddParameterBlock的作用作用一:…...
day57 集合 List Set Map
List实现类 List接口特点:元素有序 可重复 Arraylist 可变数组 jdk 8 以前Arraylist容量初始值10 jdk8 之后初始值为0,添加数据时,容量为10; ArrayList与Vector的区别? LinkList:双向链表 优点࿱…...
蓝桥杯:真题讲解3(C++版)附带解析
报纸页数 来自:2016年七届省赛大学C组真题(共8道题) 分析: --画出报纸长的样子,如果我们在上面多画一张报纸,那么就符合题意的5,6,11,12。 观察这张图:观察3…...
继续预训练对大语言模型的影响
翻译自文章:Investigating Continual Pretraining in Large Language Models: Insights and Implications 摘要 本文研究了大型语言模型(LLMs)中不断学习(CL)的不断发展领域,重点是制定有效和可持续的训练…...
关于空频变换的知识点
1.DCT变换: 离散余弦变换是一种将图像从空域转换到频域的技术,它可以将图像分解为频域分量。对于RGB图像,它由红色(R)、绿色(G)和蓝色(B)三个通道组成。当应用DCT变换时…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
