多角度思考 创造性思维 几乎整个Byteland王国都被森林和河流所覆盖 题

题目描述：

几乎整个Byteland王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫Bytetown。
在Byteland国，有n个伐木的村庄，这些村庄都座落在河边。目前在Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。 木料被砍下后，顺着河流而被运到Bytetown的伐木场。Byteland的国王决定，为了减少运输木料的费用，再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown了，它们可以在 运输过程中第一个碰到的新伐木场被处理。 显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。
注意：所有的河流都不会分叉，也就是说，每一个村子，顺流而下都只有一条路——到bytetown。
国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一块木料每千米1分钱

第一行 包括两个数 n（2<=n<=100），k（1<=k<=50,且 k<=n）。n为村庄数，k为要建的伐木场的数目。除了bytetown外，每个村子依次被命名为1，2，3……n，bytetown被命名为0。
接下来n行，每行包涵3个整数
wi——每年i村子产的木料的块数0020（0<=wi<=10000）
vi——离i村子下游最近的村子（或bytetown）（0<=vi<=n）
di——vi到i的距离(km)。（1<=di<=10000）

输出包含一行，即最小的运费。

题解：

很简单的一道题,关键是两点:第一,树形dp的加维的方法,我们下面u为根的子树不会弄,就是因为如果u没有建立节点,那么就不知道通往谁了,因此我们要再开一维来描述他的上一层中的建立的节点.第二:注意读懂题目中的题意,水流只能忘深度低的地方流,就是说,dfs处理fa的儿子们的时候,儿子们建立的节点是不会相互影响最优选择的,因为不能往下面流.因此本题就很简单了.

重点：

多开一维来记录上一层节点.注意读题,不能往下面流. 如果可以往下面流的话这道题应该怎么做呢?????

代码：

最后

以上就是仁爱百褶裙为你收集整理的多角度思考 创造性思维 几乎整个Byteland王国都被森林和河流所覆盖 题的全部内容，希望文章能够帮你解决多角度思考 创造性思维 几乎整个Byteland王国都被森林和河流所覆盖 题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。