郑重声明：本人并不自认为“会”此题，只是AC了，说说自己程序的思路而已。

原题：http://hi.baidu.com/astar/blog/item/fe22ab18c3c54b0635fa4192.htm

首先要对输入的数据进行预处理，按照“有连续的X个颜色为Y的小球”的格式，将连续的同色小球一起考虑。s[i]表示第i组小球的数量，type[i]表示第i组小球的类型。注意，所有连续的大于等于M个小球，都可以等价地当作M-1个小球来处理。

设计状态为v[i,j,k1,k2]，表示第i组小球到第j组小球的左边多了k1个与s[i]同色的小球右边多了k2个与s[j]同色的小球时被完全消去的最小代价。平凡的状态包括：i>j时，状态的值为0；s[i]+k1>=M时，状态的值为v[i+1,j,0,k2]；s[j]+k2>=M时，状态的值为v[i,j-1,k1,0]；i==j时，状态的值为M-(s[i]+k1)。

对于非平凡的状态，只需要考虑最左边的一组小球或最右边的一组小球如何处理。以左边的这组小球为例，可取的策略有两种：使用M-(s[i]+k1)个小球将它们单独消去；设s[i]与s[x]同色，在[i+1..x-1]这个序列被先行消除后，将这组小球与s[x]合并后再消除。右边的小球也可以同样定义这两种策略。还有一种策略就是，当s[i]与s[j]同色时，将[i+1..j-1]这个序列先行消除，再将s[i]、s[j]以及k1+k2个小球同时消除。状态转移方程如下：

v[i,j,k1,k2]=min{
M-(s[i]+k2) + v[i+1,j,0,k2];
M-(s[j]+k2)+v[i,j-1,k1,0];
v[i+1,x,0,0]+v[x,j,s[i]+k1,k2] (if type[x]=type[i]);
v[i,x,k1,s[j]+k2]+v[x+1,j-1,0,0] (if type[x]=type[j]);
v[i+1,j-1,0,0] (if type[i]=type[j]&&s[i]+s[j]+k1+k2>=M);
v[i+1,j-1,0,0]+(M-(s[i]+s[j]+k1+k2)) (if type[i]=type[j]&&s[i]+s[j]+k1+k2<M);
}(i<x<j)

很麻烦吧……我也觉得很麻烦。 如果谁能简化一下那真是太好了。

这样的话，一共有O(N^2*M^2)个 状态，每组状态的转移需要O(N)的时间，总复杂度是O(N^3*M^2)，不就严重TLE了么……话是这么说，也许这道题就能告诉我们Big O这种关于复杂度上界的分析有时是会不靠谱的。

具体实现时一定要采用自顶向下的DP实现，也就是所谓的记忆化搜索了。这时你会发现，实际需要计算出来的状态只占总状态数的一小部分。我对这题的4320个数据做了简单的统计，需要计算的非平凡状态的数量平均为2057.766个，其中此数量为0~1000的有2244个，1001~5000的有1541个，5001~10000的有393个， 10001~20000的有139个，20000以上的只有3个，最多的需要计算26621个状态。

我想这个题应该可以得到一个比O(N^2*M^2)更好的需要计算的非平凡状态数的上界，可本人算法分析的能力有限，希望有高人能够在这一点上指教一二。

最后说一下空间问题，如果开一个200×200x20×20的四维数组的话似乎太浪费空间了，另外，由于“内存分页”等我也不太理解的原因，程序的空间用量对实际运行时间（并非“用户时间”或CPU时间）是有影响的。我采用的方法是每次动态分配一个N*N*M*M的一维数组，用来模拟四维数组。例如状态v[i,j,k1,k2]在这个数组中的下标就应该是((i*N+j)*M+k1)*M+k2。当然，也可以将它理解成一种没有冲突的hash——将取值有限制的四元组映射为一个整数。对于本题的数据来说，我的程序最多时用了4128KB的空间。

于是，这道题的4320个数据就被比较完美的解决了。注意我并不是说这道题被完美的解决了，因为算法的理论复杂度仍然很高，不能保证无法设计出达到理论复杂度上界的数据。

欢迎批评指正。

zuma.rar 这是我做的cena评测包，内有我的程序，数据由陈启峰提供，共10组输入输出文件，每个输入文件中含432组数据。

从未实现过的：

Dinic算法（网络流）：NOI Profit等。
Stoer-Wagner算法（最小割）：UVA 10989。
Trie图（字符串自动机）：SPOJ WPUZZLES、POI #7 Virus、Ural 1158、Ural 1269。
块状链表（链式数据结构）：NOI的题。

以前实现过，但是需要活用的：

线段树的题目：PKU 3225。
平衡树的题目：NOI的题。

6月份的前两周把它们做完。

本列表收集算法资料丰富的网站，目前仅收英文网站。排名不分先后。

http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures，基本上各种数据结构和算法都会有介绍，个别的介绍太简短，没提供什么有用信息，大多数词条还是蛮有价值的，特别是有些More Information里面的链接。

http://www.research.att.com/~njas/sequences/ 在线数列百科全书。我只能说……谁用谁知道。

http://compgeom.cs.uiuc.edu/~jeffe/ Jeff Erickson教授的个人主页。这个教授真是一个好人，把自己的课程的一切资料——讲义、试题——放了上去。比如说那份详实的Algorithms Course Materials就是一份不可多得的好资料。

http://www.csse.monash.edu.au/~lloyd/ Lloyd Alison教授的个人主页。我发现里面关于某些东西（例如Suffix Tree）的介绍很不错，还有Algorithms->2D->Life里面的东西你一定要看看。

http://www.introductiontoalgorithms.com/ 一个关于Introduction to Algorithms这本书的网站，上面有用的资料不比原书中多。不过若你没有这本书，只是想对于某个算法找到其定义或者伪代码，这个网站还是有用的。

http://www.cs.fiu.edu/~weiss/ Mark Allen Weiss教授——Data Structures and Algorithm Analysis in C/C++/Java 等书的作者——的个人主页。这里有这些书的源代码，我认为这些代码是很好的。

http://www.cs.kent.edu/~rmuhamma/ Rashid Bin Muhammad教授的主页，里面的Algorithms页面挺有料。

http://courses.csail.mit.edu/ 一份MIT的课程列表，其中的6.851很神奇。

http://www.math.ucla.edu/~tom/ Thomas S. Ferguson教授的个人主页，我在上面下载了一份不错的Game Theory讲义。

哦……这个列表目前很短，因为我很菜，知道的东西还很少。如果你知道包含好的算法资料的网站，请一定要留言告诉我哦！

煎蛋：http://jandan.net/，当我打算看点儿东西用来放松时的首选方式。

草莓周刊：http://memedia.cn/，反正我觉得真是很好看。

那吒Anothr：http://anothr.com/，我目前最喜欢的RSS解决方案。（我的页面：http://anothr.com/tianyi。）

还有一些“非法”甚至“反动”的，就不说了。

第23章

调试本身并不是改进代码质量的方法，可以认为它只是一种补救措施、不得已的手段。在OI中应该尽量避免调试，应该在一开始避免错误的发生。调试的效率在人与人之间有巨大差距，所以培养调试能力十分有必要。

寻找缺陷和理解缺陷是调试中最费时的步骤。事实上在这点上不应该吝惜时间，一定要确保已经完全理解缺陷后再开始动手修改。

把需要尝试的事情在纸上逐条列出，这也许是一个加速调试得好途径，因为调试时的人大多都昏头昏脑的，最好有一个能让你保持清醒的东西。

优先检查最近修改过的代码。尽量对程序保持全局理解。永远不要随机地、尝试地修改代码，每一处代码改动都需要有明确的理由。一次只做一个改动。

心理因素让人看到他“希望”看到的东西，这对调试的影响有点大，所以要保持优秀且一致的编程习惯，要让变量名之间的“心理距离”尽量远。

把编译器警告级别设为最高，这是默认的。Profiler也可以当作调试工具，有时从不正常的运行时间或调用次数中可以看出错误。

第24章

一帆风顺的软件项目是神话，实际中的代码是经常需要经受剧烈变化的。好在实际中引起变化的（最？）重要原因——需求的变化——在我们的OI中不会出现，只要你别读错题了。

软件演化的基本准则是，演化应当提升程序的内在质量。

重构的定义是“在不改变软件外部行为的前提下，对其内部结构进行改变，使之更容易理解并便于修改”。需要重构的理由在OI中同样充分的有：代码重复，冗长的子程序，嵌套过深，过长的参数列表，命名不当。

特定的重构方法很多，也很系统，但在OI中还是应该尽量在一开始就写出更好的代码，毕竟你没有太多时间。

如果确定要对代码——特别是正确（指不可能WA）的代码——进行某种大幅度的修改（不一定是重构），一定先备份一下。

第25章

性能调整在OI中也许没有你一开始想象得那么重要，似乎复杂度才更王道。任何情况下“性能”都不是头等大事，正确性才是。

程序需求方面，就是可能不切实际的复杂度分析，少数时候实际运行时间无法用理论复杂度衡量。程序的设计就是基本的算法了，如果这里面出了致命问题，再多的代码调整也无济于事。最后的手段才是代码调整。

代码调整的问题在于，高效的代码并不一定就是“更好”的代码。80/20法则是一定要注意的，Profile一下嘛……“随时随地”的优化是绝对不可取的。

常见操作的相对效率那个表真是好东西。它说我们整数的赋值、整数的加减乘、浮点数的加减乘、调用一个函数、用下标访问数组等操作所需的时间都相差无几！这还真是惊人的结论……（有空还是自己验证一下。）

优化前，一定要保存代码的可运行版本。

第26章

OI中可以考虑的代码调整技术：用查询表替代复杂表达式（没用过呢还）、使用惰性求值（常用的思想）；展开（这个很有点意思）、哨兵值（这个我比较喜欢）、把最忙的循环放在最里层（可能被忽视的常识）、削减强度（值得注意）；尽量减少数组引用、使用缓存机制（事实上很高级的东西，值得简单地尝试）；利用代数恒等式（如果真的有而你没发现的话……）、削弱运算强度（常用的）、使用正确的常量类型（以前没有注意过，也许真的很重要）、删除公共子表达式（为了程序清晰也应该做）；把子程序写成内联（“现代”计算机说这样做不一定就会性能提升）。

第19章

在表明bool值的时候，应该采用true和false而非1或0。如果从“理论”的方面论述这一点，可以说1和0是“神秘数”而true和false就不是。

比较长的判断语句中的bool表达式是一个容易出错的地方。在bool表达式方面降低复杂度的方法有：把它提炼到一个函数里然后忘掉它、试图用DeMorgan律简化它、用括号使它更清晰。

要理解很多语言中对于&&和||运算都有“短路求值”的处理，如果想避免它可以使用&和|。

按照数轴的顺序编写数值表达式，也就是说写MIN<i&&i<MAX而非i>MIN&&i<MAX。

在写复合语句时先写好开头和末尾的大括号，再填充内容。一种良好的习惯是将if、for后面跟的一条语句也放到一个单独的块里。

在程序中要避免三四层以上的深层嵌套，因为他们带来可能不必要的思维复杂度。可以考虑的解决方法有：重复判断一部分条件（违反DRY原则，故似乎不大可取）；重构某些代码到子程序中（这个比较好）；使用break语句的小trick；试图转化为一组if-else-if语句。

结构化编程就是仅仅是用顺序、选择、迭代三种控制结构的编程方法学。控制流是复杂度来源的很大一个方面。度量（思维）复杂度有一种简单的方法，但在OI中大多时候是没必要这样度量的。

第20章

软件质量的特性中有很多是与OI无关的，外在特征中也就正确性和效率需要注意，内在特征几乎都不用过多考虑。软件工程学之所以存在，很大程度上就是因为这些特征是互相矛盾的。

有时靠阅读和检查代码发现错误会比测试高效得多，极限编程(XP)的结对编程和代码检查是降低出错率的重要手段。在OI中不妨借鉴这一点，当发现错误时，先不忙着调试，先把代码看一遍。但是这样做的前提似乎是代码风格应该足够优秀，能被轻松地理解，甚至能被速读。

第21章

协同构建这部分内容，或许ACM/ICPC选手可以从中得到启迪，但对于目前的OI还是一点用途都没有。

第22章

测试在OI中最主要的体现是自己编些数据来测试正确性，这比较接近于集成测试。但与单元测试的思想类似的方法似乎也是应该应用的，也就是在编写完一个感觉上很易错的模块时应该马上独立地测试它。

第12章

有向图就是边是顶点的有序对的图，也就是说每个边都有起始顶点和终止顶点。任意两顶点间有且仅有一条边的有向图叫竞赛图。若任两顶点间都可以沿有向路径互达，图就是强连通的。

无向图的强连通定向就是把每条边指定一个方向，然后保证得到的有向图是强连通的。强连通定向存在当且仅当原图中没有桥。构造出这一强连通定向事实上很简单：按照一遍DFS的访问方向给边定向就可以了（书中的算法一如既往地麻烦）。

核心分配问题是这样的：n个商人，每人有1个商品，每人对所有n个商品按照自己的喜好进行排序。求一个把n个商品分配给n个人的方案，使不存在几个商人的集合，他们把分到的商品再次进行交换后可以使每个人都更满意。算法是：每个商人对自己最喜欢的商品的主人连一个有向边，找一个圈（由于每个点都有出边，所以这肯定是能找到的），按照这个圈进行分配，把已分配的顶点删掉，所有指向这些顶点的边重新计算。

网络就是存在源点s和汇点t的有向图，其中每条边都有一个可以认为是“容量”的权值。网络中的流定义为加在每条边上的一个函数，也就是说给每条边指定一个“流量”。合法的流应该满足：每条边的流量不超过其容量，除源点和汇点外，点的出边的容量和与其入边的流量和相等。流的净流量就是源的出边的流量和或汇的入边的流量和。求一个合法的净流量最大的流就是最大流问题。

网络的割是一组边的集合，满足把这些边从原图中删去后从源点到汇点不再连通。最小割就是边的权值（就是上述“容量”）和最小的割。最大流最小割定理的内容就是：网络中的最大流的值等于最小割的值。

求解最大流问题和最小割问题可以采用残量网络增广路的方法。这在很多很多资料中都有很好的介绍。《组合数学》这书似乎并不是学网络流的好教材。

第13章

χ(G)是图G的色数，就是说给图的每个顶点赋一个颜色使所有边的两个端点的颜色不同，需要的最少颜色数目。它也可以理解成将顶点划分成若干个集合，使每个集合的导出子图都是零图的最少集合数目。求图的色数很困难。

关于图G的色多项式pG(k)，也就是说将图G用k种颜色的方法数。有一个结论：设T是一棵n阶树，则pT(k)=k(k-1)^(n-1)。它的证明也简单：第一个顶点有k种着色方式，以后每添加一个与当前顶点相邻的顶点都k-1种着色方式（因为它仅与一个顶点相邻），根据乘法原理得证。另外，n个顶点的零图的色多项式是k^n。求色多项式的一种方法是：当G不为零图时，设x、y是一对邻接顶点，设G1为原图去掉边x、y的图，G2为原图将x、y合并成一个顶点的图（原来与x或y相邻的顶点均与新顶点相邻），那么就有pG(k) = pG1(k) – pG2(k)，递归求解即可。这个算法的正确性还比较好理解的，不过显然它是指数级的算法。它可以采用非递归的方法实现，就是维护一个图的集合，每次取出一个非零图的元素把它分成两个元素。

平面图就是可以“画”在平面上而且边不交叉的图。（更“数学”的定义似乎书上没有。）它有一些很好的性质：设一个连通的平面图的平面表示有n个顶点点、e条边曲线、r个所围区域，则：n+r-e=2。证明的方法是先对树证明，再往树上加边，保持等式始终成立。一个平面图必存在一个顶点，它的度至多是5，这是欧拉公式的推论。

五色定理是：一个平面图的色数至多是5。这个可以比较简单地证明，主要根据上面的欧拉公式的推论来利用那个特殊的顶点做突破口。它的加强版本四色定理也是成立的。

图的独立集的定义是一个顶点的集合，它的导出子图是零图。图的独立数α(G)就是图中最大的独立集的大小。求图的独立数很难。图的控制集是一个顶点的集合，它满足所有不在集合中的顶点都与集合中的点有边。最小的控制集的大小称为图的独立数dom(G)。图的团就是一个顶点的集合，它的导出子图是完全图。图中的一个团是图的补图的独立集，反之亦然。图的团数ω (G)是最大的团的大小。将图的点集划分成最少的团的数目称为团划分数θ(G)。完美图满足它的任何一个导出子图有χ(G)=ω (G)且α(G)=θ(G)。

图的弦就是连接圈的两个顶点且不属于该圈的一条边。如果每一个长度大于3的圈都有弦，图就被称为弦图。所有的弦图都是完美的。所有的区间图（定义不说了）都是弦图。

以上定理的证明均略，因为第一我也搞不太懂，第二它们在OI中似乎没什么用。

图的顶点连通度κ(G)是最少删去多少个顶点可以使图不再连通，定义κ(K_n)=n-1。边连通度λ(G)是最少删去多少条边可以使图不再连通。再设δ(G)表示图中顶点的最大度，则有显然的不等式κ(G)≤λ(G)≤δ(G)。

顶点连通度κ(G)不小于k的图称为k-连通图，一个图是2-连通图与以下结论等价：没有关节点；任两个顶点a、b都存在一个包含a、b的圈；每三个顶点a、b、c，都存在一条连通a、b且不经过c的路径。这些都很好证明。

关于图的点连通度的Menger定理的内容是这样的：设k是一个正整数，G是一个阶为n≥k+1的图，则G是k-连通的当且仅当对任意两个不同的顶点a和b都存在连接a、b的k条路径使得每对路径只有a和b两个公共点。

第14章

直线型代码有两种，一种是语句之间有（可能是极隐蔽的）前后依赖关系，另一种是顺序无关的语句。

对于依赖关系的语句，应该设法让这种依赖关系表现得极为明显，比如说第二个函数调用的参数是第一个函数调用的返回值，或者说它们有共同的（按引用传递的）参数。当然，也可以用数据来表明没有依赖关系的语句。

至于顺序无关的语句，也应该尽量让相关（操作于同一对象）的语句放在一起。也就是说，应该让越靠近的语句关系越大。

第15章

if语句的一种常见用途就是区分正常情况与异常情况。应该把正常情况放到if前面然后异常情况用else处理，这是一种好的习惯。但我认为如果所有的代码逻辑都是异常情况用if，似乎也不会带来太大困扰。特别是在遇到异常情况就会return的情况，先处理了所有异常情况，然后在“净室”的环境下写正常情况的代码，减少了缩进层次，似乎也会更清晰。这是我的编程习惯。

if-then-else语句串的排列一般采用常见的情况在前的方式来处理，这样可以（很不明显的）提高效率。case语句是类似的。提倡尽量在每一case语句后都break，否则很容易令人困惑。

第16章

循环有好多种，不过在OI中选择哪一种似乎是自明的。应该尽量避免在循环体内外重复语句，虽然有时候看上去是不可避免的。

循环的控制语句和循环的内部最好应该可以互相看作黑盒，完全分离。

循环的初始化代码应该紧紧放在循环前面。当这种代码进有一句时，把它放到for的第一个语句似乎是更好的选择。

尽管C中的for很强大，但是一般应该让循环头中的语句仅与循环控制相关。其实还是循环的控制和循环的内容分离。

使用continue可以避免一个能让整个循环体都缩进的if判断。

减少off-by-one错误的好方法是在脑海或者用纸笔模拟，对于优秀的程序员来说这不应该太费时。

我觉得在OI中采取从内而外编写循环的方法学不是个好主意。

第17章

如果能增强可读性，那么就使用return。

对于goto，我的观点是：永远不要用。事实上我坐到了这一点。

第18章

表驱动法是一个好主意，应该了解。其实OIers对于这种东西应该比一般的“程序员”熟些，大部分情况下，不就是一预处理么，呵呵。

1，《组合数学》《Code Complete》两书看完并写完全部的缩写/笔记，这个尽量快些，每天都要有进度。

2，后缀数组要会O(n)算法，height相关的东西要写熟；后缀树的话，至少会个O(nlogn)吧，要多做几道相关的题。串处理方面一定要加强，看论文，看CLRS。

3，做SGU，所有1000+的题目要都做掉，然后写一个阶段的总结。然后开始做600+的，尽量也都做掉。看看有没有相关的好玩儿的数据结构/算法（估计不太有）。

4，本月暂时不学Vim和Linux。

5，不能荒废时间，放松一下可以，你知道怎么样算荒废时间。

第9章

这一章讲二分图中的匹配。给出了几个能启发思路的转化成二分匹配的模型：有禁止的棋盘上放非攻击车；有禁止的棋盘上放1×2骨牌；m个具有一定资格的人申请n个工作。将问题转化为二分图匹配模型的关键点是构造二分图，使可行解与合法的匹配一一对应，这样最优解一般就对应了最大匹配。

定义二分图的交错路径是这样一种路径：含有奇数条边，其中仅有第1条、第3条、……、最后一条边都没有包含在当前的匹配方案里，仅有路径的两个端点没有被匹配。一个匹配是最大匹配当且仅当不存在交错路径。求最大匹配的方法就是不断寻找交错路径并将使用其中的奇数边重建当前匹配方案的，这就是Hungary算法。书中给出的伪代码垃圾了，本来不用那么麻烦的，更好的代码参见我以前关于Hungary算法的文章

二分图的最小覆盖的意思是这样的：选定一些点，让所有的边都有端点被选择，选的点数尽量少。König定理是这样的：二分图的最大匹配数等于最小覆盖数。这个定理可以帮助解决另一类可以转化为二分图匹配模型（先转化为最小覆盖模型）的问题。

一个和二分匹配有关的问题叫稳定婚姻系统。似乎在OI中用途不太大（主要是不太具扩展性），问题和算法（延迟认可算法）我不描述了。

（第10章暂略）

第11章

图就是由顶点和边构成的东西，（无向或有向的）边可以认为是顶点中的一种（可交换或不可交换的）关系。顶点的度就是邻接的边的数量，如果是有向图的话还可以定义入度和出度。

欧拉路就是一条经过了所有边仅一次的（不一定是简单）路径。存在欧拉路的充要条件是有0个或2个度为奇数的顶点，前者的欧拉路的起点与终点是闭合的。欧拉路可以用圈套圈算法来求。不过书中的方法实现起来还是麻烦（需要写链表），有更好的方法。中国邮递员问题，就是求一条从一个点出发经过每一条边再回到起点的最短路径。解决这问题的大概想法就是通过添边把所有奇度顶点变偶。问题的算法书上没写，不过我想大约就是：找出所有奇度顶点求它们两两的最短路，然后求（非二分图的……）最优匹配。如果是有向的反而简单的多，因为这样可以根据负点和正点构造出二分图匹配。

Hamilton路径的定义就是一条经过所有顶点仅一次的路径。这是NP-Complete问题，目前没有多项式算法。

判断图是否是二分图只需要试图给图2涂色，如果涂出矛盾了就不是。

树是一种图，它的定义包括：任两点都有且仅有一条路径的图；不含圈的图；n个顶点n-1条边的连通图。

Shannon开关游戏很有意思。正方必胜策略的有无取决于图是否存在两个不存在重复边的生成树，如果找出了这两个生成树，必胜策略的算法还是不太复杂的。不过这两个生成树怎么找呢？

求最短距离树，其实就是求单源最短路径，所有的最短路径（可以）是一棵源点为根的树，用Dijkstra算法求。最小权生成数用Kruskal算法或Prim算法求。