关于传说中的"树型动态规划"在讨论题目的时候CC提及过。最近有幸找到一篇论文，相当激动，发现这个东东也比动态规划本身更容易理解。
先来看一个比较有挑战性的题目：）
战略游戏
Problem
Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。
他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。
注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。
请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵.
Input
第一行为一整数Ｍ，表示有Ｍ组测试数据
每组测试数据表示一棵树，描述如下：
第一行 N，表示树中结点的数目。
第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)。
接下来k个数，分别是每条边的另一个结点标号r1，r2，...，rk。
对于一个n(0<n<=1500)个结点的树，结点标号在0到n-1之间，在输入数据中每条边只出现一次。
Output
输出文件仅包含一个数，为所求的最少的士兵数目。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
这个题目是04年高二准备NOIP的时候看到过，当时打死没有想出有效的解决方法。然后就拿着题目去问我们廖老师，廖老师一拿到题目题目还没看完，立马给出了解决方案：不会考这么难的题。于是这个题目也就遗留了下来，没想到事隔这么多年以后又重新见识了这个题目，倍感亲切，呵呵~。
这个题目看上去想图论，贪心是明显错误的。用动态规划的思想可以很有效地解决。就看你能不能看出来是动态规划。就像杨潇说的：动态规划这类题，别人一说就明白，自己就很难想到。
在给出这个题目的状态转移方程之前，我们先从更简单的树型动态规划入手，看看其他一些题目。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
二叉苹果树
题目
有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树
2 5
/ /
3 4
/ /
1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式
第1行2个数，N和Q(1<=Q<= N,1<N<=100)。
N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。
每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。
输出格式
一个数，最多能留住的苹果的数量。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
分析：因为树是二叉的，所以状态转移方程很容易写出，
我们用a[i][j]描述树，f[i][m]表示第i个节点下，共保留m个树枝的最大苹果数目。
方程：f[i][m]=mas{ f[L][n]+f[R][m-n-2]+a[i][L]+a[i][ R]} 0<=n<=m-2 其中L,R为i的左右子树
选课
[问题描述]
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
输入：
第一行有两个整数N,M用空格隔开。(1<=N<=200,1<=M<=150)
接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。
输出：
只有一行，选M门课程的最大得分。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
分析：这个题目是一个普通的树，关键步骤就是把这个普通的树转换为一颗二叉树，并且处理的时候特殊处理一下右子树。我自认为普通树转化为二叉树以后很难处理各个节点的辈份关系，但是对于这个题目来说，如果节点1,2,3都是节点0的孩子,那么转换后便成了这样:
0 0
/ | / ----> /
1 2 3 1－2－3
辈份虽然变了，但是还是有办法处理的。
方程：f[i][k]表示第i个节点下总共选择k门课的最大得分。s[i]表示课程i的得分。则
f[i][k]=max{ s[i]+f[i.L][j]+f[i.R][k-j-1] , f[i.R][k] } (0<=j<k)
其中后边那个f[i.R][k]就是处理转换为二叉树时的关系的。
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
看到这里，树型动态规划应该可以有个初步了解了，那么我们回到最初的那个题目"战略游戏"。
分析：首先选定一个节点作为根，然后从叶子向上DP，对于每个节点来说，分别记录它放士兵和不放士兵，其子树的最少士兵数。如果该节点放士兵，则不会制约它的子树和父亲，但是如果不放士兵，则会其子树和父亲都会影响。所以在设计动态转移方程的时候要有开阔的思路。
方程：f[v][0],f[v][1]分别表示节点v没有士兵和有士兵时，该子树中最少的士兵数。方程分两个
f[v][0]={ ∑f[v.Son][1] } //若该节点不放士兵,则它的孩子都放士兵
f[v][1]={ ∑min{ f[v.Son][0], f[v.Son][1] }+1 } //若该节点放士兵,则它的孩子可以放士兵也可以不放
这样问题便完美解决了,时间复杂度O(n2)
下面再来一个题目作为思路扩展,和刚刚的题目类似:
没有上司的晚会
背景
有个公司要举行一场晚会。
为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司
（上司的上司，上司的上司的上司……都可以邀请）。
题目
每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。
输入格式
第1行一个整数N（1<=N<=6000）表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
接下来每行两个整数L，K。表示第K个人是第L个人的上司。
输入以0 0结束。
输出格式
一个数，最大的气氛值和。
Read full article from 树型动态规划 - Tiaotiao的技术专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment