本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp 背包
题意:有n个点的无根树,有m个用户,其中1号为电台,2到n-m为中转站,n-m+1到n是用户,另外用户一定是树的叶子。树的每条边有权,信号从1出发传播出去每走过一条边电台都会耗费金钱。一个用户,如果向他发送信号,那么他会对应地付钱,但是如果你不向他发送信号,他是不给钱的。最后就是,在保证电台不亏本的条件下,尽量向多的用户发送信号,问最多的用户数
这其实就是个权衡的问题,从1到每个叶子(用户)需要的花费cost可以知道,而每个叶子的价值val知道,选这个叶子的话,电台的收益其实是val-cost。要电台不亏钱,就是最终收益>=0。这种问题,一看就是背包嘛。一个叶子选或不选,选了要付出代价也有价值,不选的话就没代价也没价值,令到最后价值最大
我们现在定义:dp[u][m],表示以u为根的子树选m个叶子的最大收益
这里需要想通一个问题,收益大,不代表选的叶子就多。但是!对于选m个叶子而言,令到收益最大,那肯定是没错的。例如,选了4个叶子最大收益是3,选了3个叶子最大收益是10,虽然10收益是大但是不代表叶子数多,我们的目标是叶子数最大而不是收益最大。但是,在选4个叶子,最大收益为3的时候,一定是最好的情况,在这种情况下,我们再考虑是否选5个,6个,7个叶子,一定是最优的(本问题的最优子结构)。
所以我们最后的答案是:dp[1][m],以1为根的子树选m个孩子的最大收益,答案是m。假设1下面有cnt个叶子,我们从cnt向1枚举,找到第1个dp[1][m] >= 0,那么就可以结束,m就是答案
转移:
dp[u][0] = 0; //不选,无代价无价值,自然无收益
dp[u][1] = val[u]; //u是叶子,只能选1个叶子,收益就是u的价值,不用代价
dp[u][j] = max(dp[v][k] + dp[u][j-k] - w); //v是u儿子,w是u–>v的边权
这题数据给出来比较特殊,可以直接建树为有根数,不同建两条边
1 |
|