树型动态规划.pptVIP

总结 树型动态规划有一个共性，那就是它的基本模型都是一棵树或者森林，为了考虑方便，一般情况下都将这个树或森林转化为二叉树，如下图，然后整个问题的最优只会涉及到左右孩子的最优，然后考虑根结点的情况，这样化简了问题，最终很容易写出状态转移方程，从而问题得到解决。 另外，并不是所有的问题一定要转化为二叉树来解决，要仔细思考的就是每个结点有些什么状态，这些结点的状态与父、子结点的状态有什么联系，也就是如何由子结点的最优值推出父节点的最优值(即状态转移方程)。 * * * * * 树型动态规划 长沙市雅礼中学 朱全民 加分二叉树 给定一个中序遍历为1,2,3,…,n的二叉树 每个结点有一个权值 定义二叉树的加分规则为： 左子树的加分× 右子树的加分＋根的分数 若某个树缺少左子树或右子树，规定缺少的子树加分为1。 构造符合条件的二叉树 该树加分最大 输出其前序遍历序列 样例 中序遍历为1,2,3,4,5的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为145. 分析 性质：中序遍历是按“左-根-右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！ 因此，假设二叉树的根结点为k，那么中序遍历为1,2,…,n的遍历序列，左孩子序列为1,2,…,k-1，右孩子序列为k+1,k+2,…,n，如下图 动态规划 设f(i,j)中序遍历为i,i+1,…,j的二叉树的最大加分，则有： f(i,j)=max{f[i,k-1]*f[k+1,j] +d[k]} 显然 f(i,i)=d[i] 答案为f(1,n) 1=i=k==j=n 时间复杂度 O(n3) 要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为i,i+1,…,j的二叉树的取最优决策时的根结点为k 最后前序遍历这个树即可。 选课 给定M门课程，每门课程有一个学分 要从M门课程中选择N门课程，使得学分总和最大 其中选择课程必须满足以下条件： 每门课程最多只有一门直接先修课 要选择某门课程，必须先选修它的先修课 M,N=500 分析 每门课程最多只有1门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱结点。 如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。 这样，问题就转化为在一个M个结点的森林中选取N个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条件。 样例分析 如图1，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了1棵树，选取结点时，从每个儿子出发进行选取。显然选M=4时，选3，2，7，6几门课程最优。 动态规划 如果我们单纯从树的角度考虑动态规划，设以i为根结点的树选j门课程所得到的最大学分为f(i,j), 设虚拟的树根编号为0，学分设为0，那么，ans=f(0,n+1) 如果树根选择1门功课，剩下j-1门功课变成了给他所有儿子如何分配的资源的问题，这显然是背包问题。 设前k个儿子选修了x门课程的最优值为g(k,x)，则有 其中: 0=x=j-1，ans=g(son(0),n+1) 构造树结构 readln(n,m); inc(m); for i:=1 to n do {父亲表示法构造树} begin readln(pr[i],v[i]); {pr是前驱结点，v价值} inc(t[pr[i]]); {t记录结点的儿子个数} ne[pr[i],t[pr[i]]]:=i; {ne记录树} end; for i:=0 to n do {ts记录每个结点后代的个数} ts[i]:=ts[i-1]+t[i]+1; procedure work(now:longint);inline; var i,j,k,bas:longint; begin for i:=1 to t[now] do work(ne[now,i]); bas:=ts[now-1]+1; for i:=bas+1 to bas+t[now] do {f[i,j]表示i子树内选j的最大价值} for j:=1 to m do begin {g[i,j]是给每个节点分配的内部背包的空间} g[i,j]:=g[i-1,j]; {i不选} for k:=1 to j do {i选k门} if g[i-1,j