集训队作业srm327解题报告

1、tfixRLE（TopCoder SRM 327）解题摘要问题描述都知道，后缀表达式（也称为逆波兰式）是一种不需要括号就能描述算术表达式的方法。对于一个单独的变量，它的后缀表达式就是本身；而对于一个表达式 A#B（这里 A 和 B 都是表达式而#是最后一次计算的运算符），它的后缀表达式是由 A 的后缀表达式，B 的后缀表达式和#连接而成的。举例来说， (a+f)*b)*(c*d)的后缀表达式为 af+b*cd*。给定一个仅有变量和运算符组成的后缀表达式。在本题中，所有的变量均由一个小写字母表示；所有的运算符都是二元的，并且均满足结合律与交换律，也就是说，对于任何一个运算符#，表达式 A、B 和

2、 C，下面的两条性质始终成立：结合律：A#(B#C)=(A#B)#C。交换律：A#B=B#A。你可以根据结合律与交换律调整操作数的顺序，举例来说，对于上面提到过的表达式：将表达式(a+f)*b)*(c*d)调整为 d*(a+f)*(b*c)。同时，后缀表达式从 af+b*cd*变为 daf+bc*。你的任务就是寻找一个最有的调整方案，使得调整后的后缀表达式的 RLE长度最小。一个字符串的 RLE 长度是这个字符串中连续相同字符块的个数（也就是说，字符串 xx+yy+zz+*的 RLE 长度为 7）。数据规模：输入表达式的长度不超过 2500。分析这道题目出现在 TopCoder SRM 327

3、 中，十分复杂，比赛时无人做出。下就来具体分析一下这个问题。面算法表达式分析+贪心+网络流时间复杂度不好计算空间复杂度不好计算首先，定义调整后 RLE 长度最短的后缀表达式为最优 RLE 表达式，它的 RLE 长度为最优 RLE 长度。知道，在有关表达式中，表达式树是一种十分有效的分析工具，因此，首先通过给定的后缀表达式建立一颗表达式树。例如，对于后缀表达式 bcb+*ab+*，建立如下图所示的表达式树。图 a建树的过程可以从前向后扫描，同时使用一个栈来存放当前信息。这步比较简单，本文就省略了。根据结合律对表达式树进行调整。注意观察图 a，可以发现红接下来，色的*的左孩子是(b*(a+b)。在

4、 RLE 长度计算规则中，多个连续的*都只算一次，因此，可以将两个*合并；同理，也可以将其与蓝色的*合并，得到如下图所示的新树。图 b具体来说，如果有两个相邻的运算符节点，并且它们相同，那么就能将它们合并，得到一个儿子的“大”节点。之所以能这样做是因为题目中的条件，所有的运算符都满足结合律！这一步实际上是一个巧妙的贪心，希望读者自己体会。现在变成了，如果根据调整过的新树得到最优 RLE 长度呢？因为有交换律的存在，所以操作数之间的顺序没有影响。以图 b 为例，可以任意安排 b、ab+、b 和 cb+的顺序从而得到一个最优的字符串。假设对于当前处理的节点，它所有的孩子节点都已经处理过了，也就是说

5、已经知道了它们的最优长度。这也要求在从底向上地处理表达式书上的个每个节点。因为在树上没有两个相同的运算符节点是相邻的，因此，对于当前处理的节点，它的一个可行的 RLE 长度就是所有子节点的最优 RLE 长度之和加 1。这是不是最优的呢？显然可能不是，因为如果某个子节点的最优 RLE 表达式中的最后一个字符和它后面的子节点的最优 RLE 表达式的第一个字符相同，那么最终的 RLE 长度就会减 1，如上图中的 b 和 ba+。这样，的顺序使得这种“相同”出现的次数最多。就需要调整所有字节点注意到如果当前处理节点的某个子节点不是叶子节点，那么它的最后一个字符一定是一个运算符，而所有后缀表达式的第一个

6、字符都一定是一个字母，因此它不可能与其后的某个子节点的最优 RLE 表达式发生“相同”的情况。具体来说，把当前处理节点的所有子节点分为两类，一类是叶子节点，也就是单独的一个变量，另一类是非叶子节点。根据上面的分析，“相同”只能是“一个叶子节点+一个非叶子节点”这种情况。这让自然地联想到了二分图的匹配！同样以图 b 为例，设当前根节点，那么就有两个叶子节点 b、b，同时还有两个非叶子节点 ab+和 cb+，“相同”将在它们之间发生！注意一下，如果有多个相同叶子节点，那么可以将它们合并成一个，如上例中的两个 b 就可以合并，这不难理解。还有一个问题就是，对于一个非叶子节点，需要知道它可以哪些字母开

7、头。因为是自底向上的处理，不妨设构已经知道了所有可以开头的字母，如对 ab+，它可以以 a 或 b 开头。下面图，如果一个非叶子节点可以以字符 c 开头，并且存在一个叶子节点为 c，那么就在它们之间连一条边，接着对这个二分图求最大匹配。求得的最大匹配数也就是最多可能的“相同”数。需要计算当前处理的这个节点的最优 RLE 序列可以以哪些字母最后，开头，有两种情况：1、可以以任何一个叶子节点开头。2、可以以任何一个未匹配的非叶子节点开头。因此需要找出所有可能在最大匹配中成为“未匹配点”的非叶子节点。因为题目中的数据规模较小，只需要将这个点删除后，再判断有没有最大匹配即可。当然，还存在更优的算法，考虑这题算法