万盛经开区建设局网站,wordpress 修改轮播,江苏核酸检测机构,制作网站的软件主要有结点选择#xff08;树形动态规划#xff09;C语言 问题描述 有一棵 n 个节点的树#xff0c;树上每个节点都有一个正整数权值。如果一个点被选择了#xff0c;那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少#xff1f; 输入格式 第一行包含一个整数… 结点选择树形动态规划C语言 问题描述 有一棵 n 个节点的树树上每个节点都有一个正整数权值。如果一个点被选择了那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少 输入格式 第一行包含一个整数 n 。 接下来的一行包含 n 个正整数第 i 个正整数代表点 i 的权值。 接下来一共 n-1 行每行描述树上的一条边。 输出格式 输出一个整数代表选出的点的权值和的最大值。 样例输入 5 1 2 3 4 5 1 2 1 3 2 4 2 5 样例输出 12 样例说明 选择3、4、5号点权值和为 345 12 。 数据规模与约定 对于20%的数据 n 20。 对于50%的数据 n 1000。 对于100%的数据 n 100000。 权值均为不超过1000的正整数。 前面也说了这道题笔者花了相当长的时间但其实细究起来最重要的就三个点 1.建树 但这道题并不是简单的单个头结点每个结点只有一个父结点的那种普通的树它实际是个无向图 2.递推式 这个难度比较小但是不太好解释 讲不清楚请原谅哈~~♪( ^ ∇ ^ *) 直接写基本思路: 深度遍历每一个结点每个结点都进行一次判断 如果取这个结点那么该结点的子结点就不取如果不取该结点那么它的子结点有两种情况可以取也可以不取 于是有状态方程 dp[x][0]表示x结点不选中时最大的权值,dp[x][1]表示x结点选中时最大的权值 状态转移方程dp[x][1] dp[x][1] dp[u][0] (u为x的子结点) dp[x][0] dp[x][0] max{dp[u][0],dp[u][1]}(u为x的子结点) 看不懂就多看几遍自己纸上画一下花点时间总是能懂的。 3。树无向图的遍历 事实上树的遍历还是比较容易的只要注意多叉树与二叉树之间的转换就很容易实现祥见上一篇博客的代码这几个字是链接 但是无向图的遍历就复杂了好多这也是这篇博客的重点 因为网上能找到的的代码基本都是千篇一律但那段代码笔者是真的看不懂~~ 但功夫不负有心人我终于找到了一篇好东西 链式前向星https://blog.csdn.net/lala__lailai/article/details/79249809 以上为链接 在这两位大佬的帮助下笔者终于搞懂了这段神奇的代码 但是很显然这种算法笔者很难学得会呀~~呜呜呜… 哎讲得乱七八糟的希望读者大大们能看懂~~ 看不懂就动笔一步一步跟着代码走相信你一定会豁jing然wei开tian朗ren的~~ 以上 /divlink hrefhttps://csdnimg.cn/release/phoenix/mdeditor/markdown_views-258a4616f7.css relstylesheet/div
