啊,同学们好,我们还是来讲动态规划,这个没完没了的动态规划。 还好这一次这个题目不是特别难,叫方盒游戏。 游戏耶。 实际上没什么好玩儿的,啊。 它说的是有 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)所对应的这个,算出来的这个值。 让我们采取这种记忆化递归的办法就能够 很好的解决这个问题。 那么具体这个程序,同学们自己回去 看一看,我就没有时间仔细去说它了。 这个程序还是 比较简单的啊。 [声音]