P5765 [CQOI2005] 珠宝 题解
思路
好题,注意到有性质:颜色数最多为 \(\lfloor\log_2 n\rfloor + 1\),有了这个性质之后直接树形 DP 糊上去就过了。
简要的证明:
标签:颜色,题解,P5765,CQOI2005,sum,珠宝 From: https://www.cnblogs.com/MoyouSayuki/p/17937932考虑一个点,显然一种颜色即可。
对于一个颜色为 \(c\) 的点,其儿子至少有 \(c - 1\) 个,且为 \(1\sim c - 1\) 的排列,这样可以感性理解是最劣的,所以对于最大颜色为 \(n\) 的树,其最坏情况下至少需要有 \(f_n\) 个点,有递推式:
\[f_n = \sum_{i = 1}^{n - 1} f_i + 1\\ f_1 = 1 \]注意到 \(f_n = 2^{n - 1}\)。
证明:
\[施数学归纳法于 递推式 f\\ 对于 f_1 = 1\\ 假设对于 n\le k,有f_n = 2^{n - 1}\\ 则 f_{k + 1} = \sum_{i = 1}^k f_i + 1\\ f_{k + 1} = \sum_{i = 1}^k 2^{i - 1} + 1 = 2^k - 1 + 1 = 2^k\\ 则当 n\le k + 1 时也成立 \]因此对于一个有 \(n\) 个点的树,其最多拥有 \(\lfloor\log_2 n\rfloor + 1\) 种颜色。