树型动态规划（树形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第三题)

巴特西

树型动态规划（树形dp）

最新文章

热门文章