算法合集之《多角度思考 创造性思维》

CTSC’2007国家集训队论文南京市外国语学校陈瑜希第1页共15页多角度思考创造性思维----运用树型动态规划的解题思路和方法的探析关键字树结构动态规划信息学奥赛摘要在近几年信息学竞赛中，需要运用树型动态规划解决的问题频繁出现，这些问题变化繁多、各类思想精华渗透其中，对选手分析问题的能力和解题创造性思维有着较高的要求，因此它在竞赛中占据了重要地位。本文将分析近几年国际比赛、全国比赛中的树型动态规划问题，重点探讨几种树型动态规划问题的解法，并从这些问题的分析过程中，提炼出解决这类问题的思想方法——多角度思考，创造性思维。旨在论述解决问题的思维过程，而不仅仅是解题方法。正文信息学竞赛中通常会出现这样的问题：给一棵树，要求以最少的代价（或取得最大收益）完成给定的操作。有很多问题都是在树和最优性的基础上进行了扩充和加强，从而变成了棘手的问题。这类问题通常规模较大，枚举算法的效率无法胜任，贪心算法不能得到最优解，因此要用动态规划解决。和一般动态规划问题一样，这类问题的解决要考虑3步。1、确立状态几乎所以的问题都要保存以某结点为根的子树的情况，但是要根据具体问题考虑是否要加维，加几维，如何加维。2、状态转移状态转移的变化比较多，要根据具体问题具体分析，这也是本文例题分析的重点。3、算法实现由于树的结构，使用记忆化搜索比较容易实现。由于模型建立在树上，即为树型动态规划。顾名思义，树型动态规划就是在“树”的数据结构上的动态规划。CTSC’2007国家集训队论文南京市外国语学校陈瑜希第2页共15页大部分动态规划题都是线性的，线性的动态规划有二种方向，既向前和向后，相应的线性的动态规划有二种方法，既顺推与逆推。而树型动态规划是建立在树上的，也相应的有两个方向：1．根—叶：既根传递有用的信息给子节点，完后根得出最优解的过程。2．叶－根：既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多，应用比较广泛当然，还有一类问题，同时需要两种遍历方向，本文的第一题就属于这类。问题描述Chris家的电话铃响起了，里面传出了Chris的老师焦急的声音：“喂，是Chris的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，Chris的父母就心急如焚，他们决定在尽量短的时间内找到Chris。他们告诉Chris的老师：“根据以往的经验，Chris现在必然躲在朋友Shermie或Yashiro家里偷玩《拳皇》游戏。现在，我们就从家出发去找Chris，一但找到，我们立刻给您打电话。”说完砰的一声把电话挂了。Chris居住的城市由N个居住点和若干条连接居住点的双向街道组成，经过街道x需花费Tx分钟。可以保证，任两个居住点间有且仅有一条通路。Chris家在点C，Shermie和Yashiro分别住在点A和点B。Chris的老师和Chris的父母都有城市地图，但Chris的父母知道点A、B、C的具体位置而Chris的老师不知。为了尽快找到Chris，Chris的父母会遵守以下两条规则：如果A距离C比B距离C近，那么Chris的父母先去Shermie家寻找Chris，如果找不到，Chris的父母再去Yashiro家；反之亦然Chris的父母总沿着两点间唯一的通路行走。显然，Chris的老师知道Chris的父母在寻找Chris的过程中会遵守以上两条规则，但由于他并不知道A，B，C的具体位置，所以现在他希望你告诉他，最坏情况下Chris的父母要耗费多长时间才能找到Chris？AShermieChrisYashiro11CB1ACTSC’2007国家集训队论文南京市外国语学校陈瑜希第3页共15页例如上图，这座城市由4个居住点和3条街道组成，经过每条街道均需花费1分钟时间。假设Chris住在点C，Shermie住在点A，Yashiro住在点B，因为C到B的距离小于C到A的距离，所以Chiris的父母会先去Yashiro家寻找Chris，一旦找不到，再去Shermie家寻找。这样，最坏情况下Chris的父母需要花费4分钟的时间才能找到Chris。输入输出输入文件hookey.in第一行是两个整数N（3N200000）和M，分别表示居住点总数和街道总数。以下M行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1Ui,ViN，1Ti1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。街道信息不会重复给出。输出文件hookey.out仅包含整数T，即最坏情况下Chris的父母需要花费T分钟才能找到Chris。分析问题抽象本题题意很明确，即在一棵树中，每条边都有一个长度值，现要求在树中选择3个点X、Y、Z，满足X到Y的距离不大于X到Z的距离，且X到Y的距离与Y到Z的距离之和最大，求这个最大值。粗略分析很显然，该题的结构模型是一棵树，而且数据量很大，很容易把这题的方法向在树形结构上使用动态规划上靠拢。考虑任意节点a时，很容易发现，如果以这个点作为题目中要求的节点Y，那么只需要求出离这点最远的两个节点即可。但是在树形结构上，计算出离某个节点最远的两个节点需要)(nO的复杂度，而我们并不知道哪个点是答案中的节点Y，所以必须枚举这个点，这样一来，时间复杂度就成了)(2nO，在N=200000时会严重超时，因此这个方法是不可行的。枚举Y点的话，会超时，是否就无法加上枚举的思想呢？可以多尝试一些思路。观察这样一棵树：CTSC’2007国家集训队论文南京市外国语学校陈瑜希第4页共15页可以把点3当作点X，点1当作点Y，点6当作点Z，这样就可以得到最大值了。因为|XY|=|YX|，故只需考虑YX和YZ这两条路就可以了。在图中来观察这两条路，可以发现分别是这样走的：YX：123，YZ：1246。来比较这两条路的行程，可以发现，都是从1先到2，然后再分开走各自的路，而且满足从2以后的经过的节点，没有重复的节点。为了方便，我们形象地将点2称为分叉点。如果枚举分叉点，能不能得到一个高效的算法呢？来尝试分析这种想法。枚举分叉点将某个点a当作分叉点时，以其为根构造一棵树，对节点Y，就有两种情况：○1Y就是节点a；○2Y在a的某个孩子节点的子树上。对于情况1，可以把它转化为情况2，只需给a加一个空的孩子节点，认为它和a之间的距离是0即可。既然a是分叉点，那么X和Z就不能在同一棵子树上，X和Y，Y和Z也不能在同一棵子树上。题目中要求的是使|XY|+|YZ|最大，也就是要求2|Ya|+|Za|+|Xa|最大。至此，思路已完全明确，对于以a为分叉点的情形，只需求出到a的最远的3个点，而且这3个点分别处于a的3棵不同的子树之中。如果采用枚举分叉点的方法的话，每次都需要)(nO的计算才行，时间复杂度就又成了)(2nO。两次遍历这里，需要改变一下思路。以点1为根，计算出要求的值后，不去枚举其它的节点，而把这棵树再遍历一遍，进行一次BFS，深度小的先访问，深度大的后访问，就保证了访问到某一个节点的时候，其父亲节点已经被访问过了。假设我们现在访问到了点a，我们现在要求的是距点a的3个最远的点，且这3个点到a的路径上不经过除a外的相同节点。显然，这3个点要么位于以a为根的子树中，要么位于以a为根的子树外。如果在以a为根的子树外，那么是一定要通过a的父亲节点与a相连的。至此，思路逐渐清晰起来。此次遍历时，对于点a，检查其父亲节点，只需求出到其父亲节点的最远的，且不在以a为根的子树中的那点即可，再与第一次遍历求得的值进行比较，就可以求出以该点为分叉点时，|XY|+|YZ|的最大值了。具体方法为，每个点记录最大的两个值，并记录这最大的两个值分别是从哪个相邻节点传递来的。当遍历到其某个孩子节点时，只需检查最大值是否是从该孩子节点传递来的，如果是，就取次大值，如果不是，就可以取最大值。这样一来，该算法的时间复杂度和空间复杂度都为)(nO，是个非常优秀的算法。21346751038453CTSC’2007国家集训队论文南京市外国语学校陈瑜希第5页共15页注意这里提醒大家注意一点，计算过程中的值和最后的结果可能会超过长整型的范围，所以这里需要使用int64或者double类型。对于树必须进行两次遍历，才能求得最终的最大值。该例题的分析中提出了分叉点的想法，是比较具有创造性的，需要从多个角度思考。因此，在平时的练习中，当对一道题目束手无策时，可从多个角度思考，创造新思维，使题目得到解决。此题遍历两次的方法具有普遍性，在许多题目中都可以得到应用：记录最大的两个值，并记录是从哪个节点传递来的思想方法。这种遍历两次和记录最大的多个值的思想是值得学习的，也是动态规划在树上进行使用的经典方法。本题的树型动态规划复杂度是线形的，但是也有一部分问题，在线形的时间内无法出解。这类问题的变化更多，从状态的确立到状态的转移，都对思考角度有着更高的要求。这里先举2个例子来说明。问题描述几乎整个Byteland王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫Bytetown。在Byteland国，有n个伐木的村庄，这些村庄都座落在河边。目前在Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。木料被砍下后，顺着河流而被运到Bytetown的伐木场。Byteland的国王决定，为了减少运输木料的费用，再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown了，它们可以在运输过程中第一个碰到的新伐木场被处理。显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。注意：所有的河流都不会分叉，也就是说，每一个村子，顺流而下都只有一条路——到bytetown。国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一块木料每千米1分钱。编一个程序：1．从文件读入村子的个数，另外要建设的伐木场的数目，每年每个村子产的木料的块数以及河流的描述。2．计算最小的运费并输出。CTSC’2007国家集训队论文南京市外国语学校陈瑜希第6页共15页输入输出第一行包括两个数n（2=n=100），k（1=k=50,且k=n）。n为村庄数，k为要建的伐木场的数目。除了bytetown外，每个村子依次被命名为1，2，3……n，bytetown被命名为0。接下来n行，每行包涵3个整数wi——每年i村子产的木料的块数0020（0=wi=10000）vi——离i村子下游最近的村子（或bytetown）（0=vi=n）di——vi到i的距离(km)。（1=di=10000）输出包含一行，即最小的运费。保证每年所有的木料流到bytetown的运费不超过2000，000，000分50％的数据中n不超过20。分析问题抽象本题的题意很明确，即建立k个伐木厂，使得把所有木材运送到最近的祖先伐木厂的费用最小。由于题目给定的是一棵树，数据规模又比较大，很容易联想到树型动态规划。状态的确立首先必须有的是当前点及以当前点为根的子树中，一共建立了多少伐木厂，但是这显然是不够的，因为这个状态中没有任何与伐木厂位置相关的信息。因此我们还需要再加一维。加上有关伐木厂的位置的信息。综上，状态定为用)_,,(klefttofromf表示把以from为根的子树中建立kleft个伐木厂，把木材全部运送到最近的祖先伐木厂，所需要的费用，并且from有一个祖先伐木厂为to_。（注意到这里to_仅仅是from的祖先伐木厂，而未必是from的最近祖先伐木厂，这是为什么呢？）这个状态虽然是3维的，但是非常清晰，为我们写状态转移方程提供了很大的方便。状态的转移状态转移分2种情况讨论：在from建立伐木厂和不在from建立伐木厂。在from建立伐木厂：即分配kleft个伐木厂给from的子结点，使得费用最小。这分配的过程，也就相当于背包问题