[树形背包+复杂度分析]LOJ2124(HAOI2015)【树上染色】题解

题目概述

有一棵点数为 \(n\) 的树,树边有边权。给你一个正整数 \(K\) ,你要在这棵树中选择 \(K\) 个点,将其染成黑色,并将其他的 \(n−K\) 个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。

解题报告

我快要废了,什么题目都做不来了。这道题如果考虑点之间的收益是很难处理的,但是你如果考虑每条边的收益的话,就是SB题了。\(f[i][j]\) 表示 \(i\) 的子树中选了 \(j\) 个黑点的最优解,然后你只需要树形背包就行了。

我快要废了,树形背包都打不来了。要注意循环的正向和反向以及数组的初值问题。

示例程序

我快要废了,复杂度都分析不来了。DP过程看起来是 \(O(n^3)\) 的,但实际上你可以认为你枚举了所有的点对,所以是 \(O(n^2)\) 的。

本文链接:https://zigzagk.top/2018/05/13/loj2124
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。