本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp 背包
题意:无根树,每条边有边权,每个点有苹果数,你可以任意移动苹果,每一个苹果走过一条边的花费就是边权,如果同时m个苹果走过一条边的花费为m*w。为怎么移动,使得整个树,每个节点上的苹果的数量的方差最小,题目下面的Hint给出了方差的公式
题目一个突破点是抛弃方差公式,那个公式是多余的,起了迷惑作用。我们回到方差的定义,其实就是令到各个点的苹果数尽量相同,最好的结果就是平均分,这样方差为0,。另外是整数,所以不能整除的话,会有一些点的苹果数多1
设全部苹果数为sum,点数为n,ave=sum/n,即平均数
num = sum % n; 如果不能整除,就会有num个点多出1个苹果,即ave+1个苹果
分析到这一步,就可以背包了
也就说,最终树的样子就是,有num个点有ave+1个苹果,把这些点称为红点,有n-num个点有ave个苹果,称为黑点,问题变成了,通过运输把哪些点变为红点哪些点变为黑点会使花费最小?
dp[u][m]表示u的子树下,有m个红点的最小花费
要计算dp[u][m]要考虑u的所有儿子子树和u这个点本身,而u这个点本身是不是红点可以放在最后考虑,在转移的时候先考虑子树
这个背包,写起来不像是一般写的树dp背包,在转移的时候会出问题(主要是利用了滚动数组),我设置了一个LL res;方便转不出错。另外一开始只考虑子树,最后才考虑u这个点本身,所以一开始转移的时候利用一个临时数组tmp[]来代替,最后再把tmp[]的信息传递给dp
整个专题方程,有些许细节,主要是运输,要考虑运多少苹果,走过一条边的花费即代码中计算的cost,在此不多说了,看代码吧,转移确实有点难度,多看几次就好
1 |
|