当前位置:首页 > 动态规划 > 树形DP > 正文
洛谷P2515[HAOI2010]软件安装
1865+

题目大意:安装软件,每个软件都有价值,都需要占用磁盘空间,有些软件要跟其他软件一起安装才会产生价值,怎么安装才有最大价值?

题目描述

现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。

但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系:软件i依赖软件Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这时只要这个软件安装了,它就能正常工作。

输入输出格式

输入格式:
第1行:N, M (0<=N<=100, 0<=M<=500)

第2行:W1, W2, … Wi, …, Wn (0<=Wi<=M )

第3行:V1, V2, …, Vi, …, Vn (0<=Vi<=1000 )

第4行:D1, D2, …, Di, …, Dn (0<=Di<=N, Di≠i )

输出格式:
一个整数,代表最大价值

输入输出样例

输入样例#1:

3 10
5 5 6
2 3 4
0 1 1

输出样例#1:

5

解题思路

把互相依赖的软件缩点成一个软件,然后用树形DP处理,注意要从子结点更新到父节点:每个结点在空间m下有不同的价值,这些不同的空间价值分别看成一个物品,要么选要么不选,更新到父亲结点;这样一层一层往上更新,汇集于根节点0。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

洛谷P2515[HAOI2010]软件安装:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!