首页 > 代码库 > 河流 tyvj1506

河流 tyvj1506

题目大意:

给出一棵n个节点的有根树,一开始 树根 是一个控制点,现在要增加m个控制点,使得总费用最少。

给出每个节点的父节点以及到父节点的距离,还有这个节点的权值, 一个节点的费用 即它的权值 乘以 离他最近的且是控制点的祖先的距离。 (控制点的费用为0); n<=100 m<=50

 

解题过程:

1.一看就是树形dp,根据数据范围,可以大胆猜测状态至少是二维,但是二维显然是不够的,因为必须描述 当前节点是谁,还有多少个控制点,且当前 最近的 控制点是谁。

2.F[i][j][k] 表示以i为根的树中,当前最近控制点为k,且还能放j个控制点 的最少总花费。答案就是F[root][m][root];

3.这是道资源分配的树形dp,那么先执行老套路,多叉树转化成二叉树。。(左孩子右兄弟表示法)

状态转移方程:

F[i][j][k]=min{F[i.leftchild][p]+F[i.rightchild][k-p-1]};