郑重声明：本人并不自认为“会”此题，只是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)更好的需要计算的非平凡状态数的上界，可本人算法分析的能力有限，希望有高人能够在这一点上指教一二。 最后说一下空间问题，如果开一个200x200x20x20的四维数组的话似乎太浪费空间了，另外，由于“内存分页”等我也不太理解的原因，程序的空间用量对实际运行时间（并非“用户时间”或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月份的前两周把它们做完。
去年在开封，我买过一本题为《密码学基础》的书。当时看了一小半就放下了，后来想看的时候又找不着了。哦……我提到这些只是想说明，其实我“漫话密码学”是绝对的误人子弟之行为。 密码学的最基本问题就是对信息进行加密。也就是说，我要给你发送一条信息，但不想让别人了解这信息的内容。我就可以把这条信息进行加密以后发送，你收到以后再进行解密，就知道了信息的内容。如果能够保证除了你以外其他任何人都没有解密这个信息的能力，那么就达到了我们的最初目的。描述得形式化一点，我们约定一个加密函数E，一个解密函数D，需要保证对于任何信息M，都有D(E(M))=M，也就是说任何被加密函数加密的信息都能被解密函数解密，也就是说D是E的反函数。 这种D和E的设计是古已有之。据说我国古代行军作战时曾经用一首五言律诗的四十个字代表常用的四十种作战行动，然后传递命令时只需要传递一个字，即使这个字被截获了，也可以防止敌人得知我们的作战命令。还有据说是凯撒用过的加密法：在一个圆盘的边上写上所有的字母，在书写信息时把每个字母以圆盘旋转一定角度以后得到的字母代替。 在现在的应用中，需要被加密的信息都是二进制数，可以设计出一种“异或加密法”，利用异或这种位运算的特性。事先约定一个二进制数，将需要加密的信息与这个二进制数进行异或运算后再发送，收到信息后只需要用同样的二进制数再进行一次异或运算，就可以得到原本的信息。 我们看到，以上介绍的几种加密法，都需要在加密信息的发送者和接受者之间作一个约定，不管这个约定是一首五言律诗、一个字母圆盘还是一个二进制数，这种约定可以称作密钥。我们的一切加密行为都依赖于密钥，如果密钥被窃取，一切加密行动都失去了意义。另外，当信息的发送者和接受者相距千里，他们应该怎样安全地传递密钥呢？我们现在就要试图找到一种避免约定或传递密钥的加密方法。 用一个相对直观的例子来说明这种方法。现在，假设我要给你寄一个装有机密物品的箱子，我们都不希望这个箱子在运输的中途被别人打开，所以，必须给这个箱子加上锁才行。但问题是，我把箱子加上锁后寄给你的同时，没有一种合适的方式给你开锁的钥匙，如果把钥匙和箱子一样给你寄过去肯定也会造成不安全。于是我们采取这样的方式：我把箱子加上一把锁以后寄给你；你收到箱子之后无法开锁，但是你可以再给箱子加上一把锁，然后把箱子寄还给我；我收到上面加有两把锁的箱子后，把我自己的锁打开，再寄给你；你最后收到的就是只有你自己的锁的箱子，你把自己的锁打开，就可以拿到箱子中的物品了。我们一共将箱子寄了三次，在每次寄的过程中箱子上都是有锁的，这样就可以避免箱子被别人打开。更重要的是，在这种方法中，我们并不用得到对方给箱子加的锁的钥匙，也就是说，不需要传递“密钥”。 用密码学的语言再叙述一次，设我的加密函数和解密函数是E1和D1，你的加密函数和解密函数是E2和D2，有恒等式D1(E1(M))=M和D2(E2(M))=M。我先把信息用E1加密后传送给你，你收到信息后用E2再次进行加密并传回给我，我收到你再次加密的信息后用D1进行解密并传送给你，你最后收到信息后用D2解密即可。这个方法的正确性依赖于这样一个恒等式：D2(D1(E2(E1(M))))=M，但这个恒等式并不是显然的，并不能由上面的两个恒等式推导出来。也就是说，并不是所有的加密函数和解密函数都可以用于这种方法，好在密码学家已经找到了好多好多可以这样应用的加密函数和解密函数。 上面的方法通过避免传递密钥的方法消除了传递密钥中可能的不安全因素。然而，事实上还有另外的方法可以用来消除这种不安全因素，那就是：设法使密钥即便被截获也不会造成任何影响。这种方法听起来不可思议，但他确实可以实现的。它的原理就是让密钥“分身”成两个，一个公钥，是可以随便传送随便被截获的，一个私钥，是永远都不会被传送当然也就不会被截获的，这就是所谓的“不对称加密”。在介绍这个之前，先让我们升级一下我们的符号系统吧。在当初只有一个密钥K的时候，对信息M的加密过程可以表示为E(M,K)，对密文C的解密过程就是D(C,K)，恒等式就是D(E(M,K),K)=M。 不对称加密就是这样一种技术，需要使用两个密钥K1和K2，若加密过程就是E(M,K1)，解密过程就是D(C,K2)，恒等式是D(E(M,K1),K2)=M。这两个密钥就是公钥和私钥，他们的特点是：用公钥加密过的信息可以用私钥解密，用私钥加密过的信息可以用公钥解密，无法使用公钥推算出对应的私钥。利用不对称加密技术来传递信息的过程大约是这样的：我要给你传送一条信息，先问你你的公钥是什么，你会把你的公钥传递给我，我把想要传送的信息用你的公钥进行加密后传送给你，你收到信息后用你的私钥进行解密。这里面存在传递密钥的过程，但是传递的只是公钥。也就是说，即便有一个人将你传递的公钥和我发送的加密信息全部截获，由于只有私钥才能解密这条信息，也无法从公钥推算出私钥，他无法进行解密。 这种不对称加密还有一个衍生的作用，就是身份确认或者数字签名。身份确认就是说，需要确认与我建立了通讯的那个人就是我想与其通讯的那个人，这个可以这样做：由于这个人是我“认识”的人，所以我肯定知道他的公钥，现在我给那人发送一条信息，要求他把这个信息加密后再发过来，如果我用他的公钥能解密出原来的信息，就证实了这条信息的确是经过了他的私钥加密的，由于私钥不会被泄漏，也就证明了与我通讯的确实就是那个人。数字签名也差不多，就是说发信息的那个人要对这个信息进行“签名”，以让收到信息的人确认收到的信息就是由他发送的，而非别人伪造；发信息的人只需对信息用自己的密钥加密一遍，收到的人确认这个信息可以被他的公钥解密，就确认了这条信息的来源。 上面只是对于密码学的“漫话”而已，要想真正的理解其中的原理需要大量的数学知识。在这里，我只希望把密码学的基本思想介绍一下，以求开阔思路、有所启迪。
本列表收集算法资料丰富的网站，目前仅收英文网站。排名不分先后。 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讲义。 哦……这个列表目前很短，因为我很菜，知道的东西还很少。如果你知道包含好的算法资料的网站，请一定要留言告诉我哦！