珠宝
P5765 [CQOI2005] 珠宝 题解
P5765 [CQOI2005] 珠宝 题解 思路 好题,注意到有性质:颜色数最多为 \(\lfloor\log_2 n\rfloor + 1\),有了这个性质之后直接树形 DP 糊上去就过了。 简要的证明: 考虑一个点,显然一种颜色即可。 对于一个颜色为 \(c\) 的点,其儿子至少有 \(c - ......
LOJ6039 「雅礼集训 2017 Day5」珠宝
LOJ 传送门 显然枚举物品做背包没有前途,于是我们把体积相等的物品捆绑在一起。 设 \(f_{i, j}\) 为考虑完体积 \(\in [1, i]\) 的物品,背包容量为 \(j\) 的最大值。可以贪心求出 \(g_{i, j}\) 为选 \(j\) 个体积为 \(i\) 的物品的价值最大值。 ......
P5765 [CQOI2005] 珠宝
思路 应该很容易想到使用树形 dp。 令 \(f_{u,i}\) 代表,只考虑 \(u\) 为根的子树,\(u\) 的编号为 \(i\) 的情况下,最小的编号总和。 那么我们可以用 \(u\) 的儿子 \(v\) 来更新 \(f_{u,i}\)。 转移方程 \(f_{u,i}=\sum_{v\in ......
如何通过小红书发现最时尚的珠宝饰品?
如何通过小红书发现最时尚的珠宝饰品? 嘿,亲爱的小伙伴们!今天我要和大家分享一些关于如何通过小红书发现最时尚的珠宝饰品的秘诀。小编我是小红书专家小紫,潮流资讯的捕手,就让我来带你们领略那些令人心驰神往的珠宝世界吧! 第一步:关注时尚达人 在小红书上,有无数的时尚达人与你分享他们的珠宝饰品心得。这些达 ......
LOJ #6039「雅礼集训 2017 Day5」珠宝
给定 $n$ 个物品,第 $i$ 个物品有体积 $c_i$,价值 $v_i$。给定 $K$,对 $1 \sim K$ 的所有 $i$ 求大小为 $i$ 的背包的最大价值。 $n \leq 10^6$,$K \leq 5 \times 10^4$,$c_i \leq 300$,$0 \leq v_i ......