关于传说中的"树型动态规划"在讨论题目的时候CC提及过。最近有幸找到一篇论文,相当激动,发现这个东东也比动态规划本身更容易理解。
先来看一个比较有挑战性的题目:)
战略游戏
Problem
Bob喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。
他要建立一个古城堡,城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。
注意,某个士兵在一个结点上时,与该结点相连的所有边将都可以被了望到。
请你编一程序,给定一树,帮Bob计算出他需要放置最少的士兵.
Input
第一行为一整数M,表示有M组测试数据
每组测试数据表示一棵树,描述如下:
第一行 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