摘要：动态规划练习题汇总题目描述传说中的九头龙是一种特别贪吃的动物。如上图中的输出输出一个整数，表示在满足大头的要求的前提下，九头龙的难受值的最小值。
动态规划练习题汇总
题目描述
传说中的九头龙是一种特别贪吃的动物。虽然名字叫“九头龙”，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。
有一天，有M个脑袋的九头龙看到一棵长有N个果子的果树，喜出望外，恨不得一口把它全部吃掉。可是必须照顾到每个头，因此它需要把N个果子分成M组，每组至少有一个果子，让每个头吃一组。
这M个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好K个果子，而且K个果子中理所当然地应该包括唯一的一个最大的果子。果子由N-1根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。
对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就是所有头吃掉的树枝的“难受值”之和。
九头龙希望它的“难受值”尽量小，你能帮它算算吗？
例如图1所示的例子中，果树包含8个果子，7段树枝，各段树枝的“难受值”标记在了树枝的旁边。九头龙有两个脑袋，大头需要吃掉4个果子，其中必须包含最大的果子。即N=8，M=2，K=4：
输入
N个果子依次编号1,2,...,N，且最大的果子的编号总是1。
果树的形态，每行包含三个整数a (1<=a<=N)，b (1<=b<=N)，c (0<=c<=105)，表示存在一段难受值为c的树枝连接果子a和果子b。如上图中的 1,2,20; 1,3,4; 1,4,13; 2,5,10; 2,6,12; 3,7,15; 3,8,5
输出
输出一个整数，表示在满足“大头”的要求的前提下，九头龙的难受值的最小值。如果无法满足要求，输出-1。如上图中的难受值为4
1 思路
2 拆分子问题
3 计算
4 代码
5 时间复杂度
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/106957.html
摘要：动态规划练习题汇总描述有堆石子排成一排，每堆石子有一定的数量。现要将堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过次合并后成为一堆。 动态规划练习题汇总 描述 有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一...
摘要：动态规划练习题总题目描述设一个个节点的二叉树的中序遍历为，其中数字为节点编号。若某个子树为空，规定其加分为，叶子的加分就是叶节点本身的分数。试求一棵符合中序遍历为且加分最高的二叉树。 动态规划练习题-总 题目描述设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及...
摘要：谈到德勤与亚马逊达成战略合作之后的进展情况，德勤中国云服务主管合伙人刘俊龙向趣味科技透露，截至目前为止，德勤已经携手，共同为二三十家大型企业提供了各种各样的数字化转型和云服务的落地，并且已经初见成效。蜀道之难，难于上青天！唐代大诗人李白这句脍炙人口的诗词，相信也是不少传统企业上云时的心情写照。不过在德勤与亚马逊AWS的携手合作之下，传统企业在上云与数字化转型时遭遇的诸多痛点，正在被逐一解决。...
阅读 4988·2021-09-07 09:58
阅读 764·2019-08-30 15:55
阅读 2843·2019-08-30 15:55
阅读 897·2019-08-30 15:53
阅读 1526·2019-08-29 12:57
阅读 1739·2019-08-26 13:46
阅读 543·2019-08-26 11:00
阅读 3615·2019-08-23 15:42
