我在这个帖子里说过nlogn求最长上升子序列的方法：
    http://www.oibh.org/bbs/viewthread.php?tid=10682
    下面引用我自己的发言：

     f表示长度为i的上升子序列最后一个数最小是多少。显然数组f是单增的。
     读到一个新的数x后，找到某个i使得x>f[i]且x<=f[i+1]，于是用x去更新f[i+1]；特别地，如果所有的f[i]都小于x，则增加f的长度。
     最后看f数组有多长就行了。
     由于f单增，所以查找i时可以用二分查找，因此时间复杂度为O(nlogn)。
     举个例子，假如序列为 3 2 8 6 7 4 5 7 3，则f数组的变化过程如下：
     3
     2
     2 8
     2 6
     2 6 7
     2 4 7
     2 4 5
     2 4 5 7
     2 3 5 7
     最后，f的长度达到4，因此答案为4。
     注意，最后的f数组不一定是最长上升子序列的一个方案。

    这里要说的这个算法利用了nlogn的最长上升子序列(LIS)的技巧：用f[k]表示长度为k的上升子序列最后一个数最小是多少。
    在最长公共上升子序列中，令f[i,j][k]表示A串前i个数字，B串前j个数字，长度为k的公共上升子序列中，最后一个数最小是多少。

    当A[i]=B[j]时，像nlogn的最长上升子序列一样把A[i]插入到f[i-1,j]中，这需要线性的时间扫一遍f[i,j]；
    当A[i]<>B[j]时，我们需要合并f[i-1,j]和f[i,j-1]，使得对于每个k满足f[i,j][k]:=min{ f[i-1,j][k],f[i,j-1][k] }。这需要线性的时间扫一边f[i-1,j]和f[i,j-1]并取k相同时的较小值。
    最后输出f[n,m]的长度（使f[n,m][k]有意义的最大的k）。
    这样的复杂度是三方的，我们需要优化。

    考虑A[i]=B[j]的情况。当i固定时，随着j的增加，插入的位置一定也在后移，因为同样是插入的A[i]，但j的增加（B串长度的增加）使得f [i,j]更优，因此可以更新的值就更靠后。于是，对于每个i，我们可以按照k的顺序扫描f[i-1,j][k] 并在A[i]可以插入f[i-1][j]的k位置时增加j，从而预处理所有A[i]=B[j]时A[i]应该插入的位置。
    再考虑A[i]<>B[j]的情况。从定义看，f[i-1,j-1]和f[i-1,j]只有一个地方不一样，因为多一个数最多只能造成一个k 的值变小；同样地，f[i-1,j-1]和f[i,j-1]也只有一个地方不一样。因此，f[i-1,j]和f[i,j-1]最多只有两个k所对应的值不相同，且当有两个不同的值时，总是f[i-1,j]中的某个值较小，f[i,j-1]中的某个值较小。这给我们优化的余地。在每次处理完f[i,j]时，我们可以记录一个值x[i,j]表示f[i,j][k]与f[i-1,j][k]中值不一样的k是多少，在A[i]=B[j]时直接赋值为插入的位置，在 A[i]<>B[j]时待后文说明。以后合并时，先让f[i,j]:=f[i-1,j]（由于此时的f[i-1,j]已经没有别的用处了，因此可以用滚动数组记录，直接令f[i-1,j]是f[i,j]，避免实际的赋值操作），然后将新的f[i,j]中的，使f[i,j-1][k]比f[i- 1, j][k]小的k所对应值更新。这个k是多少呢？显然应该是x[i,j-1]。这样的操作同时可以确定x[i,j]=x[i,j-1]。
    这样，复杂度就达到了平方。

    附参考的资料（原来从这篇论文里学到的，不知道有没有此类的中文资料，估计没有才在这里写了一个，感兴趣的话可以下载附件仔细研究）

点击下载此文件

Matrix67原创
转载请注明出处

http://www.zombo.com/

    终于感到做一件大事很难。搞几次模拟赛还不算大事，比起搞模拟赛的举办平台差远了。此时我终于理解了VVS当初的难处。还记得Vijos才发展起来时，各种评论的声音都有，可想当时VVS发展这个OJ的艰难。最后Vijos走到了今天，经历的是近一年的风风雨雨。
    这次模拟赛的争议相当大。首先让我不满的是Vijos上出现了许多赛中讨论的帖子，答案都快讨论出来了。再后来出现了一个很XX的帖子，回了20多个；帖子本来是冲着我来的，结果后来基本上和Super Master干起来了。有时想一想，这也算是Vijos文化的一部分吧，毕竟Vijos也是从混乱中走过来的。不同的网络交流平台有不同的文化，比如 Vijos的讨论就明显与论坛不一样，而且这里面也产生了相当多的专用词汇和“内部笑话”。现在Vijos已经比较稳定了，该是维护纪律、创造特色文化的时候了。而这要比以往任何一项技术性操作复杂得多。
    令人欣慰的是OIBH上大多数人反应并没有参加讨论。有一个第二题随机化过4个点的人感动得我痛哭流涕。在OIBH上听到的支持声更多。

    这次模拟赛的题的确很猥琐。
    交题时VVS就拿了一段第一题的样例说这个很猥琐。幸兄预言情书这玩意儿将在OIBH掀起一次十分败坏人品的讨论。这次模拟赛的主要争议都在第一题。
    第二题这样的估计以前也从来没有过。很多人敢想不敢做，很多人想都不敢想。Vijos上有人建议给出一个不同排法导致不同结果的例子，某人回帖说难道都是一样，一人再回说要真是这样就好了。
    第三题完全是原创，一点参考都没有（最多算一个上次xg的第一题）。编这个题目时想了很久，题目叙述改了很多次。
    许多人反应第四题在某某地方出现过。这是很正常的，因为这是一个经典问题。不过我还是要算原创（dd_engi说我厚颜~~），至少数据是我自己出的，网名和手机号都编进去了。这个游戏确实很好玩，我的Palm还在时上课就玩这个，里面有500个Puzzle，好像做到接近200时Palm就崩了。我评讲这个题时为了说明题意并且演示题解里给出的搜索优化方法，投影到大屏幕上玩了一会儿；满以为大家都会去做做这个被我设成难度5的题，谁知后来居然全开始玩这个游戏了。

    搞个模拟赛确实不简单啊，自己校对了十几次。估计我是属于那种完美主义者了吧，不能容忍任何一点小错误。完美主义者并不一定是好事。
    有人问我NOIp前还搞不。我想应该还会吧，至少还有一次。

    Lost第三季来了，本来要和尚猫一起看的，结果小猫不要我了。看我在你的Space上发你在KFC的照片。
    24第六季的预告片http://www.24trailer.com/，倒计时还有17天才能看。这个新花样还玩得不错，让期待中的人有了更迫切的盼头。明年1月14和15，4小时的Premiere。等啊等啊等。