啊，同学们好，我们还是来讲动态规划，这个没完没了的动态规划。 还好这一次这个题目不是特别难，叫方盒游戏。 游戏耶。 实际上没什么好玩儿的，啊。 它说的是有 N 个方盒，摆成一排。 每个方盒可以有自己的颜色。 连续摆放的同颜色方盒就构成一个大块儿。 下面这个图里面一个个小块都是方盒。 那么连续摆放的若干个方盒，比如4个这是一个大块儿。 那我们这图里面一共就有4个大块儿了。 那你怎么玩儿这个游戏呢？ 很无聊的吧？ 你每次去点击一个方盒， 你点了这个方盒，这个方盒所在的大块儿呢，它就会消失。 你点它，这个就会消失了。 那如果消失的大块儿中共有 k 个方盒，那你就能获得 k 平方个积分儿。 然后这游戏就问你了，给定，开始时的状态。 你作为一个玩家，最多可以获得多少的积分儿？ 这里面有聪明的玩法，是吧？ 那我们说，这实际上是一个，这个， 动态规划的这个问题。 你不会写程序，你还玩不了这个游戏。 那么这个输入第一行就是test的case啦，然后每 一组数据有两行，第一行就是有多少个方盒，然后第二行就是每一个方盒的颜色。 它是按从左到右的顺序给出来的。 然后你要对每一组数据求这个最高分儿。 额，这个样例输入输出没什么可看的啊。 那我们看一下基本思路啊。 那一开始一共有 n 个大块儿。 我们考虑的是 一个个的大块儿，而不是独立的这个方盒，对吧？ 我们先算出 从原始的数据推算出有多少个大块儿，然后我们把这些大块儿给它编号。 从左到右编号依次为 0 到 n-1。 那这个第 i 个大块儿的颜色就是 color[i] ，我们要记住，对吧？ 那它包含方块儿的数目当然就是 len[i] 了。 那我们先粗略地想一下。 我假设我想用 click_box(i) 表示从 大块 0 到大块 i 这一段消除以后所能得到的最高分儿。 那整个问题当然就是求 click_box(n-1) 对吧？ 但是你会发现，你从 这个思路想下去，你没有办法形成一个递推的关系。 这个 click_box(i) 跟 click_box(i-1) 之间有什么关系呀？ 跟 click_box(i-n) 什么之类的有什么关系啊？ 就想不出来了。 所以我们就要把这个 click_box 这种描述方法给它稍微细化一点。 所谓细化就是复杂化，也就说加个什么条件。 也就是说我们这个用来描述状态的这个 维度要增加一维，那表现在这个 click_box 上面相当于它的参数多了一个。 我们用 click_box(i, j) 表示从编号为 i 的这个大块到编号为 j 的这个大块，这一段 包含 i, j 啊，被消除以后所能得到的最高分儿。 那这时候整个问题呢，就是 click_box(0, n-1)，对吧？ 那我们要解决这个问题，我们要解决的问题是 click_box(i, j)。 那我们按照递归啊或者动归的思路我们都在想我们先走一步，然后看看事情会变成什么样。 那我们怎么走这第一步呢？ 你可以考虑，我这第一步是对最右边的那个大块 j 进行处理。 这就叫走一步。 那我们对这个大块儿 j 进行处理，它实际上是有两种处理方式，对吧？ 我们要取其优的。 第一种处理方式，鲁莽，就是直接消除它。 那你直接把它消除以后，消除这个 j 这个大块，你所能得到的分数是 len[j] * len[j]，对吧？ 然后，接下来你就要把 j 左边的那些大块儿全部都消完了。 那剩下来的问题就变成，我要消除 j 左边所有的大块儿所能得到的最高分儿是多少，然后把两部分加起来。 那消除 j 左边的大块儿，这个问题实际上就是 click_box( i, j-1)，唉我们看到这个问题跟原来的原始问题 啊这个形式相同但规模变小了，这是一个好现象。 但这只不过是 第一种处理方式。 就是鲁莽的将其直接消除，它会不会是好的办法呢？不一定，不用高兴的太早。 那我们再看，对这个右边的大块 j，实际上它还有第二种处理方式。 第二种处理方式就是，我不急着把它消掉。 我指望以后它说不定能跟左边的某个同色大块合并。 那样说不定还能得到更多的分数，对吧？ 我们知道，我们合并从越长的这个大块儿，我们一下把它消掉， 得到的分数当然就比这个大块分别几个部分分别消除 分数要高，对吧？ 所以我们会期望，期待，j 和它左边的某个同颜色大块儿合并。 但是 j 左边的同颜色的大块儿可能有好多个，我到底跟哪个大块儿合并会比较好呢？ 那我只好枚举，对吧？ 左边同颜色大块儿有很多个。 我们要枚举，到底和哪一个大块儿合并。 那我们假设这个 j 和左边的大块儿 k 合并。 那左边的大块 k 是什么？ k 就介于 i 到 j-1 之间，对吧？ 它是小于 i-1 的，小于 j-1 的。 那 j-1 的颜色必然和 j 的颜色不一样，否则就是同一个大块 了，对吧？ 所以这个 k 是大于等于 i，小于 j-1 的。 那这样的 k 可能有多个，我就要枚举这个 k。 对每一个 k 我们都看一下。 我们把大块 j 和大块 k 合并所能得到的最高分是多少，然后我们选一个最优的。 那么，我们把这个 j 和这个大块 k 合并。 所能得到的最高分是什么呢？ 到底是不是我写的这个式子呢？ 这个式子表示什么啊？ 这表示，我们先看最后这一部分儿，这部分说的是这个 j 和 k 合并了。 合并了以后呢，我把 j 和 k 一起消掉，这就能得到了一个分儿，对吧？ 那么我们要做到把 j 和 k 合并，首先我就要把这个 从 k+1 到 j-1 这一部分给它合并，对吧？ 那从 k+1 到 j-1 这一部分它也有各种 各样的合并方式。 其中最优的合并方式所能得到的分数我们记为click_box(k+1, j-1)。 它跟，原问题形式一致，规模变小了。 然后还有就是这个 k 左边的那些东西也要全部删除，对吧？ k 左边 的那些东西全部删除，所对应的问题就是 click_box(i, k-1) 了对吧？ 这时候所能得到的最高分就是这样。 那我们整个大块 j 跟 k 合并起来所能得到的最高分儿看起来就是这个东西。 这到底对不对呢？ 来想想啊。 啊显然是不对的。 为什么不对啊？因为我给大家讲这个 公式的时候我已经事先说了，这个 k 和 j 合并成一个大块以后，一起把它消掉所能得到的分数是这个东西。 但问题是k 和 j 大块合并以后，我们为什么就要一下子把它消掉呢？ 我们为什么不能把它留着，再让它等着跟左边的其他同颜色大块进一步合并呢？ 是吧？完全可以这么做嘛。 但是你要这么做的话，用 click_box 怎么描述下面的这个，这样的一个问题呢？ 就描述不了，于是就无法递推下去了。 这时候怎么办呢？ 按照我们的法宝，就是 click_box 对问题的描述还不够细化。 它只有2个参数， 也就是2个维度还不够细化，我们就要加一个什么限制条件，让它变成有3个参数，然后我们- 说不定就可以形成递推关系了。 那我们怎么来进行进一步的细化，就添加新的维度呢？ 我们这么搞一种新的形式，就是 click_box(i, j, ex_len)。 增加了一个新的维度，对吧？ click_box(i, j, ex_len) 表示什么呢？ 表示在大块 j 的右边已经有一个长度为 ex_len 的大块。 那这大块怎么来的我们不管它，可以，可能是在合并的过程中形成的， 对吧？ 那这个长度为 ex_len 的大块我们暂且就称为 ex_len。 而且这个 j 的颜色和 ex_len 相同。 注意这点啊。 我们从这种情况下将 i 到 j 以及 ex_len 全部都消除所能得到最高分儿就是用 click_box(i, j, ex_len) 表示。 那时候整个问题变成什么呢？ 整个问题当然就变成了这个 click_box(0, n-1, 0) 对吧？ 然后， 因为这个 n-1 最后一个大块儿它右边只有长度为 0 的什么 大块了对吧？ 它右边根本就没东西，所以就相当于它右边有一个长度为 0 的大块。 那根据这个式子，我们就能够写出递推关系了。 那我们要求 click_box(i, j, ex_len) 我们还是 按照这个原先的想法，我们走一步。 走一步处理什么呢？ 我们这一步就是要处理 j 和 ex_len 合并以后的大块，这个大块 Q。 j 和 ex_len 的颜色是一致的，对吧？ 我们肯定要把它合并。 不会把它们分别处理。 我们把它合并以后的大块称为 Q。 现在我们在所做的第一步就是要处理这个Q。 我们对这个Q，实际上也有两种处理方式。 一种方式就是鲁莽的给它消去。 另外一种方式，就是指望这个 Q 将来和 j 左边的什么大块再去合并。 好，那么将 k 直接消除，这种做法所能得到的最高分儿是什么呢？ 首先把这个 Q 消除以后，所能得到的分数就是 len[j] + ex_len的平方，是吧？ 那么，剩下来就是要把 j 左边的那些大块全部都消除，那时候所能得到的最高分儿就是 click_box(i, j-1, 0)。 为什么是 0 啊？因为 j-1 这一块右边都已经消完了，对吧？ 所以 j-1 右边就没有什么大块了，所以它右边的那个大块的长度就是0。 好，这是直接将 Q 消除的这个做法。 那还有一种做法就是我们不着急，Q 我留着，指望它跟 这个 j 左边的某个大块 k 去合并。 那 j 左边可能有好多同颜色的大块，对吧？ 那我们就要枚举这个 k， 看看跟哪一个 k 合并所能得到的分数最高，我们就取最优的。 我们要枚举 可能和 Q 合并的大块。 我们假设大块 k 和 Q 合并。 那 k 是什么？ k 是在 j 的这个左边的啊。 那么 k 的取值范围当然就是从 i 到 j-1。 那么， 假设我们这个 Q 和 k 合并，那这个时候所能得到的最大分数是什么呢？ 我们可以把它写出来，就是这么一个式子。 它为什么是这么一个式子呢？ 是，这式子两部分分别表示什么呢？ 我们先看这个click_box(k+1, j-1, 0)， 这个是说明什么问题？ 就是你希望让这个 Q 和 k 能够并在一块儿。 那显然，k 和 Q 之间的那些大块儿你必须把它消除掉。 那 k 和 Q 之间的大块儿要消除掉也有各式各样的消法，其中最优的消法它能得到的分数当然就是cli- ck_box( k+1, j-1, 0)，对吧？ k 和 Q 之间的大块儿他们的编号当然就是，就是从 k+1 到 j-1，对吧？ 那这个 j-1 右边它到底有没有和 j-1 同颜色的大块呢？ 它不存在这个问题。 因为 j-1 的右边就是 j，j 是 Q 的一部分。 Q 是要将来留着跟 k 去合并的，所以 Q 是跟 k+1 到 j+1 之间的块如何去消除毫无关系的。 所以说我们把 k+1 到 j-1 这一部分消除，这个事情跟 j-1 右边的东西都没有关系，所以 描述这个问题实际上就是click_box(k+1, j-1, 0)，因为这个问题跟 j-1 右边的东西毫无关系。 好，这一部分就说的是，把 k 和 Q 之间的这些大块给它 消除。 那 k 和 Q 之间的大块被消除以后， 剩下的部分变成了一个什么样的问题呢？ 这时候 k 和 Q 就合在一块了对吧？ 然后，k 和 Q 就合在一块了，但是 i 和 k ，从 i 到 k 之间的大块 依然还没有消除。 那这个时候，剩下的部分问题实际上就变成了click_box(i, k, len[j]+ ex_len)。 这代表什么意思呢？就是有从 i 到 k 这么多大块都有待消除，而且 k 的右边是一个大块儿。 这个大块儿呢，它的长度为len[j]+ex_len。 为什么长度是 len[j]+ex_len呢？ 这个大块儿不就是 Q 嘛，对吧？这个大块就是 Q。Q 的长度不就是， 就是，j 的长度加上 ex_len，对吧？ 由于这个 Q 的颜色跟 k 是相同的， 它又会被跟 k 合并，所以剩下的问题就是click_box(i, k, 等于这一块就是 Q，Q 的长度就是len[j]+ex_len是吧？ 就是这个 k 的右边会有一个大块，这个大块就是 Q，它的长度是len[j]+ ex_len，然后 Q 的颜色跟 k 一致，将来 k 就会跟 Q 合并。 好啦，那现在我们就写出这个递推式了，对吧？ 就是对这个大块 Q 进行两种方式处理的时候我们都能够写出递推式。 然后我在里面取一个最优的就行了。 当然第二种情况我们就需要枚举这个 k 了。 对吧？ 那现在递推式就写出来了，那接下来我们就要考虑 这个递归的终止条件是什么，对吧？ 比如我要求这个click_box(i, j, ex_len)的时候 什么时候就能不用递归直接就能得到答案呢？ 递归终止条件是什么，当然这个终止条 件还是比较好分析的。 就是 i=j 呗，你要求click_box(i, j, ex_len)，如果 i=j 那就剩下一个大块儿了，那还不好办吗？ 就不用递归了，是吧？ 就这样。 那， 思路我们就说完了，程序呢就不仔细说了。 因为我们写一个递归 函数它有了这个终止条件又有了递推公式我们就能够写出来了，对吧？ 但是这里面要注意的是，你不能完全用递归的方式去写。 如果用递归 方式会有大量的重复计算，于是就超时了。 所以这道题目我们可以采取 所以的记忆化的递归的办法。 我们用一个score数组，用来存放 这个计算结果。 这个score什么 i, j, k 实际上就相当于这里的click_box(i, j, k)所对应的这个，算出来的这个值。 让我们采取这种记忆化递归的办法就能够 很好的解决这个问题。 那么具体这个程序，同学们自己回去 看一看，我就没有时间仔细去说它了。 这个程序还是 比较简单的啊。 [声音]
