树型动态规划 - NOCOW

树型动态规划

来自NOCOW

跳转到： 导航, 搜索

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

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

基本上有这样一个步骤：

一、有根树：

      1.建树（一般以递归方式实现，有时数据过大以BFS方式实现） 

      2.在建树中找到叶子的时候特别赋值。 

      3.回溯时通过方程确定出每个节点的最优值并记录。 

      4.遍历完整棵树后一般以根节点值作为最终值。 

补充:关于建树，有很多时候会将原来的多叉树改造为左孩子右兄弟的二叉树，以下两道例题用到了这种改造。

例题1:Tyvj P1051 选课

例题2:Vijos P1518 河流(IOI2005 Rivers)

--澹台彦澍 02:08 2009年9月8日 (CST)

//简单的改造代码:         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第三题)

Read full article from 树型动态规划 - NOCOW