树型动态规划(树形dp)

树型动态规划就是在“树”的数据结构上的动态规划,树型动态规划是建立在树上的,所以有二个方向: 1.根—>叶:这种题目基本上碰不到 2.叶->根:根的子节点传递有用的信息给根,完后根得出最优解的过程。这种的题目是树型动态规划的最常见类型。 首先定义

       无根树:题目中可以以任意节点为根建树,经过动态规划后即可直接得到最优值。
有根树:必须以某一个节点为根建树才能通过动态规划后得到最优值。

基本上有这样一个步骤:

一、有根树:

      1.建树(一般以递归方式实现,有时数据过大以BFS方式实现)
      2.在建树中找到叶子的时候特别赋值。
      3.回溯时通过方程确定出每个节点的最优值并记录。
      4.遍历完整棵树后一般以根节点值作为最终值。
补充:关于建树,有很多时候会将原来的多叉树改造为左孩子右兄弟的二叉树,以下两道例题用到了这种改造。
例题1:Tyvj P1051 选课
例题2:Vijos P1518 河流(IOI2005 Rivers)
//简单的改造代码:
for i:=1 to n do
if ft[root[i]]=false then//这个节点目前还没有孩子
begin
a[root[i]].left:=i;//把这玩意儿放到当前节点的左边
ft[root[i]]:=true;//标记-有孩子了
num[root[i]]:=i;//该节点当前最后一个孩子
end
else//有孩子了
begin
a[num[root[i]]].right:=i;//把这玩意儿给他当前最后一个孩子的右边
num[root[i]]:=i;
end;//By 澹台彦澍

二、无根树:

      1.随机定根,重复有根树过程
2.要枚举节点作为根的情况重复有根树过程。
例题:Vijos P1100 加分二叉树(NOIp2003第三题)
上一篇:重装yum


下一篇:Java 并发和多线程(二) 多线程的优点 [转]