翼若垂天之云

今天上午十一时左右抵达郑州，为NOIP2007。
现在在河南省实验中学的机房，老师和同学们对我太好了，还可以在这里上网。
明天就NOIP2007了，这会是我OI生涯中的最后一场正式比赛。我知道这次比赛对我真的意义不大，但我还是希望得到一个完美的成绩，希望看到一场完美的谢幕。
昨天写了《我为何中止写作DP系列文章》，同时在blog上和OIBH上发了。评论让我感慨太多。我本来以为，有些失望至极的人会大放厥词。没想到几乎所有人给的评论都非常正面，都是些鼓励、支持和理解的话语。有些话甚至让我热泪盈眶。
有人说：只有在迷茫中才能进步！
有人说：DD 的自省力让我折服了。
有人说：背包9讲我认认真真读了4遍，每遍都有新的感觉…….
有人说：任何人用真诚的态度做的东西都是受人尊敬的，更何况您在OI中有着众所周知的才华。
让我感慨最深的留言中说：沿着这条路走下去，也许您牛也会成为一代宗师。
的确，自从NOI2007结束以来，我已很久未能燃起熄灭殆尽的野心了。总是想着，随便找个大学，随便学点自己喜欢的东西，随随便便过完平淡稳定的一生，就行了。可是为什么，为什么我从未想过“成为一代宗师”？
总得有点理想的，对吧？理想高远一点没有什么错的，对吧？
为什么不能，试着，向最高处努力？
为什么不能像Alan Turing那样？
为什么不能像John von Neumann那样？
为什么不能像Edsger W. Dijkstra那样？
为什么不能像Bjarne Stroustrup那样？
为什么不能像Linus Torvalds那样？
为什么不能像Richard M. Stallman那样？
为什么不能像Donald Knuth那样？
为什么不能像Gang of Four那样？
为什么不能像CLRS那样？
为什么不能像所有那些早已成为计算机科学天空耀眼星座的名字那样？
我不相信，新兴的计算机科学已经早早衰老。
我不相信，算法的宝库已被掠劫一空。
我不相信，已经没有新的编程语言需要发明。
我绝不相信，我绝不相信有什么人注定平庸！
是的，将理想定高一些，将眼光放远一些。那些都不是真正值得作为最高追求的，离开这个国家也好，获得美好爱情也好，并非最重要的。最重要的是，思想。建立自己的思想，将它尽量长久地留存在这个世界上。也就是说，至少应该为成为“思想巨匠”、“一代宗师”而努力。
在文化路的“计算机书店”买了<Tao of Programming>，虽然里面很多鬼话，但还是值得一读，作为程序员的心灵鸡汤，作为计算机科学家的寓言。
看到了<Write Great Code>的前两卷，真是好书，写出这样一部大书的人可以一生无撼了。

Tags: NOIP, 书籍, 河南省实验中学, 理想

Related posts

迷茫 [20080527]
七月的第一天
听合唱音乐会有感及其它
4月17日，2008
ACM新手上路总结及感言

前几天，在写作《动态规划中的线形模型》时，写到了讨论LIS问题的章节。顿悟一般，理解了LIS的数学本质。原来LIS问题就是这样一个问题：
一个有限集S，其中定义了两个全序关系<1和<2，用这两个全序关系定义一个偏序关系<：x<y当且仅当x<1y且x<2y。求偏序集(S,<)的最长链。
没错，这就是LIS问题的数学本质。知道了这个以后就可得出很多关于LIS及相关问题的结论。由于本篇文章并非教程，对这些结论不详加解释。

在原本的LIS问题中，第一个全序关系是“序列中x在y的前面”，第二个全序关系是“x小于y”。如果我们按照第二个全序关系对序列进行排序，可以得到原问题的一个对偶问题。即：对原序列进行排序，再把排序后序列的每个元素换成在原序列中的下标。两个对偶问题的答案是一样的，也就是说原序列中的LIS长度，肯定等于得到的新序列中的LIS长度。而对偶问题有一个非常好的性质：它的序列中的所有元素都在1..N中取值。这就带来了很多很多种O(NlogN)算法的思路，比如说可以用virtual binary tree。
既然LIS的本质是要求“偏序集的最长链”，那么就可以应用组合数学中有关的定理。例如熟悉的定理：最长链的长度等于反链的划分数；以及其对偶定 理：最长反链的长度等于链的划分数。所以LIS中那个让很多人不理解的结论就昭然若揭了。为何上升子序列的覆盖数等于最长不上升子序列的长度？因为上升子序列是链，不上升子序列是反链。
所有可以转化为LIS问题求解的OI题目一定满足LIS的数学本质。也就是说，需要用LIS的算法解决的题目，一定能找到两个全序关系，和由它们定义的偏序关系。例如那道经典的给定一些矩形造一座塔的问题，为什么按照矩形的长排序然后求宽的LIS。原因很简单，两个全序关系就是由矩形的长和宽定义的，而LIS就是要先按照其中一个全序关系排序以得到序列。
可以对LIS的数学本质进行扩展，也就是对LIS问题进行扩展，例如<1和<2不一定都得是全序关系，可以有一个是偏序关系，这个偏序关系也可能是另外两个全序关系定义的，等等……这样又可以解决更多题目，例如“三维导弹拦截”。
……

LIS问题其实只是线型动态规划中非常简单的一个模型，通过思考它的数学本质，竟然就可以得到如此多的结论，由这些结论就可以编制出无穷无尽的OI题……这让我欣喜异常。
然而，LIS的数学本质中涉及到的离散数学中的概念：全序、偏序、链，这都是我还非常非常陌生的概念。连这些概念都不敢说懂，我怎么敢说我懂了LIS问题？我怎么敢写出一份涉及它的教程？
是的，通过深入的思考，我充分理解到：动态规划的每一个模型，都可能有着深不见底的数学本质；不掌握足够多的数学工具，就不可能从本质上把握动态规划。
可我掌握的数学太少了，特别是用处特别大的离散数学，只是浅尝辄止。我深感现在的能力无法写出一份好的动态规划总结。更让我恐慌的是：竟然有那么多人，会那么仔细地，甚至带着崇拜的眼光，阅读我的总结。
由于数学能力不足，也为了避免误人子弟，我已经中止了DP系列文章的写作。今天发布的《背包问题九讲v1.1》是今年的最后一次发布。
我对期待着《动态规划中的线形模型》的所有人表示无比愧疚的歉意。你们高看了我，我目前的能力不足以从本质上把握诸多线形模型，更不足以写出好的总结。对不起，让你们失望了。
但是，要注意我说的是“中止”而非“终止”。那个雄心勃勃的计划没有夭折，只是暂时停顿了。在将来的某一天，在我自认为数学能力足够的时候，也许是在我加入某个ACM-ICPC队伍的时候，我会继续未完成的计划。动态规划的领域是如此迷人，哪怕需要再长的时间，我会将这个写作计划完成。
最后，再次向所有失望的人表示真诚的歉意。

Tags: LIS, OI, 理想

Related posts

USACO Training 通关
ACM新手上路总结及感言
OIBH杯OI邀请赛8.04
4月7日人品爆发，及其它
我的USACO心得