2003集训队100道讨论题block解题报告

1、IOI2003 中国国家集训队难题活动0004Block解题省芜湖市第一中学【题目大意】给定一串共 n 个整数，其中某些整数可能相同，整数的数值称为这个数的“颜色”。对于这些整数，可以进行“消除”的操作，也就是把续同色整段中所有的整数一起从串中去除，所谓“连续同色整段”，就是原串中一段连续且同色的整数，而且段的左端是整个串的左端或者左端的左边相邻的整数和这一段不同色，且段的右端是整个串的右端或者右端的右边相邻的整数和这一段不同色。每次“消除”操作有一个得分，等于消除掉的整数的个数的平方。对于给定的整数串，求把所有整数消除掉能够得到的最大分值。【解决情况】采用动态规划解决，时间复杂度为 O(nm

2、3)，其中 m 为原串中所有连续同色整段的个数；空间复杂度为 O(n3)。【算法梗概】定义动态归划的状态为 Maxi,j,k，代表把(i,j,k)扩展子串中的整数全部消除能够得到的最大分值（定义见正文），则每个 Maxi,j,k可以在 O(n)级时间内求出。最后的Max1,m,0的值。就是【正文】首先把读入的数据进行压缩，也就是把所有的连续同色整段依次收集起来，每一段用它的颜色和长度来表示。设压缩后的连续同色整段表示为(color1,len1),(color2,len2),(colorm,lenm)。每次消除操作会将续整段从串中去除，也就有可能把它两边的连续整段（如果同色的话）合并起来，也就是

3、：连续整段有可能在操作的过程中增长。为了体现这种效果。我们定义“扩展子串”的概念。定义 1：(i,j,k)扩展子串是指原串中从(colori,leni)到(colorj-1,lenj-1)的连续同色整段以及在一系列合并操作后长度增加了 k 的连续整段(colorj,lenj+k)依次排列的一个串。i,j,k要满足 0i=j=m 以及 0=ki)的值可以通过某些合法的 Maxi,j,k求出，且(j-i)(j-i)。证明：对于扩展子串(i,j,k) ，着眼于在消除过程中最后续段(colorj,lenj+k)的用途，可以分为两种情况：情况 1： (colorj,lenj+k)不和任何一个段合并，单独

4、消除，于是可以先把这一段消除掉，然后再把前面所有的段消除掉，在这里消除的顺序不影响结果。这种情况下得到的最大分值是 Maxi,j-1,0+(lenj+k)2 。 显然这里用到的 i=i,j=j-1 ， 满足 0i=j=m，Maxi,j,k是合法的状态，并且(j-i)(j-i)成立。情况 2： (colorj,lenj+k)和前面的某些段合并，不单独消除，假设与 j 合并的位置最靠后的一段为 p，当然，colorp=colorj且 i=pj-1，因为 j-1 段部可能与 j 同色。注意到这些段处在一个一维的空间里，也就是说，j 这一段要想与 p 这一段相遇，那么必须先把它们中间所有的段都消除掉。

5、 也就是说， (colorp+1,lenp+1) 到(colorj-1,lenj-1)这些段和其他的段不会了，可以单独消去。而消去中间的段之后，j 这一段就合并到了 p 段的末尾，使 p 段变成了(colorp,lenp+lenj+k)。这样，此情况下得到的最大分值是 Maxi,p,lenj+k+Maxp+1,j-1,0。这里用到的第一对 i=i,j=p，满足 0i=j=m，并且(j-i)(j-i)；第二对 i=p+1,j=j，也满足 0i=j=m，并且(j-i)(j-i)。注意：这两种情况中 k的很容易看出来。最 后续 段 在 消 除 过 程 中 的 用 途 只 有 这 两 种 情 况 ，

6、所 以Maxi,j,k=maxMaxi,j-1,0+(lenj+k)2，Maxi,p,lenj+k+Maxp+1,j-1,0后一项要考察所有的colorp=colorj且 i=pj。由于情况一和情况二中计算Maxi,j,k都只用到了一些合法的状态Maxi,j,k且这些 i,j都满足(j-i)(j-i)，所以定理 2 得证。结论 3：所有合法的 Maxi,j,k都可以在 O(nm3)的时间内计算出来。证明： 采用动态规划，以 d=j-i 为阶段，边界条件是当 d=0 时，根据定理 1 求出所有 i=j 的状态值。d 从 1 开始递增到 m-1，每个阶段计算所有合法的 Maxi,i+d,k。根据定

7、理 2，每个阶段的状态计算都只用到以前状态的值。状态转移的方程也就是定理 2 中所给出的。由于 0i=j=m，0=k=restj=n，故状态数规模为 O(nm2)，每次状态转移需要枚举 i=pj-1，进行情况 2 的计算，(j-i)m 故转移的时间复杂度为 O(m)。因此所有合法的 Maxi,j,k都可以在 O(nm3)的时间内计算出来。根据结论 3，很容易就可以设计出算法了：Step 1:读入整数串并进行压缩，得到所有的连续同色段。从后向前计算出所有的restj值，以便在后面动态规划的计算中确定 k 的范围。Step 2:计算出所有合法的 Maxi,i,k作为边界条件。Step 3:从 1

8、到 m-1 枚举阶段 d，对每个阶段，计算出这个阶段包含的所有合法状态。计算方法见结论 3。Step 4:输出 Max1,m,0。做到这里，算法成型，但是程序事先的细节上还是有一定的优化余地的：在计算 Maxi,j,k时，本来采用枚举 p 从 i 到 j-2 判断，但事实上只有当 colorp=colorj时才有用，所以可以事先对每个位置 j 计算出 Prevj，代表 j 之前的最后一个与 j 同色的位置，这样计算时可以直接顺着 j 找到 p=Prevj，p=Prevp知道求出某个 pi 为止。这样在相同颜色不是出现很多的情况下可以大大提高程序速度。对于这类动态规划的题目，关键是要合理定义状态的意义，使状态值能够表示最终的答案，每个状态值都可以正确无误地从以前阶段的状态值推知。特别是这题，“消除”操作对整个串造成的影响比较大，比较全局化，更要缜密思考，使状态值的计算有理有据，各种情况的分类无遗漏，才能得出正确的算法。本题解决到了这里，就告一段落了，最终算法的时间复杂度为 O(nm3)，于 O(n4)；空间复杂度为 O(n3)。程序见 block.pas。情况下等【进一步研究的方向】本题是一道开放性的题目，所以并不知道到底算法能够做得多好。就本文中算法来看，O(nm3)还没有达到很好的地步，应该还可以找到复杂度更低的算法。本文