当前位置:首页 >> >>

NOI导刊树型动态规划_图文

树型动态规划
长沙市雅礼中学 朱全民

加分二叉树
? 给定一个中序遍历为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几门课程最优。

转化为二叉树
? 如果该问题仅仅只是一棵二叉树,我们对儿子的分配就仅 仅只需考虑左右孩子即可,问题就变得很简单了。因此我 们试着将该问题转化为二叉树求解。
? 图2就是对图1采用孩子兄弟表示法所得到的二叉树

动态规划

? 仔细理解左右孩子的意义(如右图): 左孩子:原根结点的孩子 右孩子:原根结点的兄弟
? 也就是说,左孩子分配选课资源时, 根结点必须要选修,而与右孩子无关。
? 因此,我们设f(i,j)表示以i为根结点的二叉树分配j门课程的所获 得的最大学分,则有,

f

(i,

j)

?

? max?
?

f f

(il , k) ? f (ir , j ? k ?1) (ir , j),根结点不选修

?

a[i],根结点选修

? 0<=k<j<n, i ∈(1..m) ? 时间复杂度O(mn2)

? 样例求解过程:初始f(i,0)=0 ? f(6,1)=6, f(5,1)=max{1,6}=6, f(7,1)=2
f(4,1)=max{1,2}=2, f(1,1)=max{1,f(4,1)}=2 f(3,1)=4, f(2,1)=max{1,4}=4 ? f(5,2)=7 f(7,2)=max{f(5,1)+2}=8 f(4,2)=max{f(7,2),f(7,1)+1}=8 f(1,2)=max{f(4,2),f(4,1)+2}=8 f(2,2)=max{f(1,1)+1, f(3,1)+1)}=5 ? f(7,3)=9 f(4,3)=max{f(7,2)+1,f(7,3)}=9 f(1,3)=max{f(4,2)+1,f(4,3)}=9 f(2,3)=max{f(1,1)+f(3,1)+1,f(1,2)+1}=9 ? f(2,4)=max{f(1,3)+1, f(1,2)+f(3,1)+1}=max{9+1,8+4+1}=13

//读入数据 ,转化为孩子兄弟表示 fin >> n >> m; score[n+1] = 0; brother[n+1] = 0; // 输入数据并转化为左儿子右兄弟表示法 for (int i=1; i<=n; ++i) { int a, b; fin >> a >> b; if (a == 0) a = n + 1; score[i] = b; brother[i] = child[a]; child[a] = i; }

void dfs( int i, int j) {
if (visited[i][j]) return; visited[i][j] = 1; if (i==0 || j==0) return; dfs(brother[i], j); // 如果不选i,则转移到状态(brother[i], j) f[i][j] = f[brother[i]][j]; for (int k=0; k<j; ++k) { // 选择i,枚举学习多少以i为根的 (j-k-1),并转移到相应状态 dfs(brother[i], k); dfs(child[i], j-k-1);
// 更新答案 if (f[brother[i]][k] + f[child[i]][j-k-1] + score[i] > f[i][j])
f[i][j] = f[brother[i]][k] + f[child[i]][j-k-1] + score[i]; } }

软件安装(2010河南省选)
? 有N个软件,对于一个软件i,它要占用Wi的磁盘空间, 它磁的盘价容值量为为VMi。计我算们机希上望,从使中得选这择些一软些件软的件价安值装尽到可一能台大 (即Vi的和最大)。
? 软件之间存在依赖关系,即软件i只有在安装了软件j( 包括软件j的直接或间接依赖)的情况下才能正确工作( 软件i依赖软件j)。幸运的是,一个软件最多依赖另外一 个软件。如果一个软件不能正常工作,那么它能够发挥 的作用为0。
? 我。们一现个在软知件道只了能软被件安之装间一的次依,赖如关果系一:个软软件件i没依有赖依软赖件则Di Di=0,这时只要这个软件安装了,它就能正常工作。
? 现在请你设计出一种方案,安装价值尽量大的软件。

分析
? 由于软件存在先后约束关系,因此简单按软件先后顺序进行动 态规划,会不符合无后效应原理,因此我们需要在进行动态规 划前进行预处理。
? 若安装软件i必须先安装j,则从i向j连一条有向弧,则软件的约束 关系就构成了一个有向图。如下图:
? 可以看出如果有k个制约关系,则有k条边,中间会存在环

分析
处理环:
? 由于环为互为前提,要选择环中的一个必须都进行选择, 因此可以将环缩成一个点,这个点为权值和价值为其他 点的和。
? 孤立点没有与其他点也没有任何关系,可以不管。 ? 如果把每个连通分量看成一棵树,则图变成了为一个森
林,图2。

树型动态规划
? 显然这个森林可以采用树型动态规划,先将它儿叉树。

? 设f(i,j)表示以i为根结点的二叉树分配j资源的最大价值

f

(r[i],

j)

?

? max?
?

f f

(r[il (r[ir

],k) ? f (r[ir ], j ? ], j),根结点不选

k

?

w[r[i]])

?

c[r[i]],根结点选

警卫安排
? 一个有N个区域的树结构上需要安排若干个警卫; ? 每个区域安排警卫所需要的费用是不同的; ? 每个区域的警卫都可以望见其相邻的区域,只要一
个区域被一个警卫望见或者是安排有警卫,这个区 域就是安全的; ? 任务:在确保所有区域都是安全的情况下,找到安 排警卫的最小费用; ? 0<n<=720;

? 分析样例
? 该图有6个区域如图1,安排情况如图2,红色点为安排 了警卫。
? 2号警卫可以观察1,2,5,6;3号警卫可以观察1,3; 4号警卫可以观察1,4;
? 费用:16+5+4=25

分析
? 对于每个点i,都有3种状态分别为: – 要么在父亲结点安排警卫,即被父亲看到 – 要么在儿子结点安排警卫,即被儿子看到 – 要么安排警卫
? 对于i – i被父亲看到,这时i没有安排警卫,i的儿子要么安排警 卫,要么被它的后代看到。 – i被儿子看到,即i的某个儿子安排了警卫,其他儿子需 要安排警卫或者被它的后代看到。 – i安排了警卫,i的儿子可能还需要安排警卫,这样可能 有更便易的方式照顾到它的后代;所以i的儿子结点被i 看到,可能安排警卫,可能被它的后代看到。

动态规划
? 设f(i,0)表示i结点被父亲看到; f(i,1)表示i被它的儿子看到; f(i,2)表示在i安排警卫;
? 则状态转移方程为:
i的儿子数
f (i,0) ? ? min ?f (ik ,1), f (ik ,2)?
k
i的儿子数
? f (i,1) ? min ?f (ik ,1), f (ik ,2)?? f [i j ,2], 其中j ? k
k i的儿子数
? f (i,2) ? min ?f (ik ,0), f (ik ,1), f (ik ,2)?? c[i]
k
? 时间复杂度O(N2)

procedure work(now:longint); var i,j,sum,tmp:longint; begin for i:=1 to t[now] do work(w[now,i]); //对每个儿子进行处理 f[now,0]:=0; //以下处理now被父亲看到 for i:=1 to t[now] do inc(f[now,0],f[w[now,i],1]); //now的儿子被儿子看到
sum:=0; //以下处理在now被儿子看到的 for i:=1 to t[now] do // now的儿子被儿子看到或者或安排警卫;
inc(sum, min(f[w[now,i],1],f[w[now,i],2]));
f[now,1]:=maxlongint; for i:=1 to t[now] do //枚举哪个儿子放警卫 begin
tmp:=sum-min(f[w[now,i],1],f[w[now,i],2])+f[w[now,i],2]; f[now,1]:=min(f[now,1],tmp); end; f[now,2]:=c[now]; //以下处理在now放置警卫 for i:=1 to t[now] do Inc(f[now,2], min(min(f[w[now,i],0],f[w[now,i],1]),f[w[now,i],2])); f[now,1]:=min(f[now,1],f[now,2]) ;{1包含了2状态,取优值} end;

总结
? 树型动态规划有一个共性,那就是它的基本模型都是一棵 树或者森林,为了考虑方便,一般情况下都将这个树或森 林转化为二叉树,如下图,然后整个问题的最优只会涉及 到左右孩子的最优,然后考虑根结点的情况,这样化简了 问题,最终很容易写出状态转移方程,从而问题得到解决。
? 另外,并不是所有的问题一定要转化为二叉树来解决,要 仔细思考的就是每个结点有些什么状态,这些结点的状态 与父、子结点的状态有什么联系,也就是如何由子结点的 最优值推出父节点的最优值(即状态转移方程)。


更多相关标签: