文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

25号某时博客突然无法访问，MJJ主站也打不开，QQ联系上MJJ询问状况，他说整个机房都掉线了，预计26号下午就能恢复...

26号下午MJJ在首页发布通知，"2009.11.26 17:40 与某运营商谈崩,因无法接受签订生死状,我们将于2009.11.27早上开始搬迁新线路."，恢复日期又延迟了，看情况应该是和移动谈崩了，QQ联系上 MJJ得知新线路是电信的，预计27号中午前恢复。此时我不得不将首页转移到通告页面...

27号下午MJJ又在首页发布通知，"14:07新机房IP已分配,请各网站管理员在下午五点前尝试PING服务器管理后台,如CP.*.****.NET即可获得正确的IP.工单在五点钟上机,估计六点前可以恢复访问."，看来恢复时间又推迟了...

傍晚，首页通知，"18:52 上架检查设置,因数量较多并且需要重新配置网络,恢复会有先后的顺序,请耐心等待.关于事件始末,我们对于某运营商表示遗憾与失望,我们并不能寄望于一家视客户权益不顾,野蛮中断行为的运营商抱有希望.因事态重大,在此不再陈述,百度即有真相. "，我所在的服务器还没恢复，但是我已经把IP指向了新服务器...

直至27号晚上21:50，博客才最终恢复访问。新的电信线路我感觉有些慢，这样没有了移动线路的优势，我在考虑是不是转到美服...

这两天看DP看得人有点烦，无聊的JAVA让人更烦，或许是辣椒吃多了，有点上火，感觉很是不爽。换换思路，下午用PHP写了一个偷懒用的玩具，以后有时间慢慢补充功能吧，也是时候写点什么东西出来了，累...

明天又是周末了，写写代码，背背英语，做份CET-4真题，简单而乏味...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

刚才用O(n^2)的DP算法做了最长上升子序列，具体见POJ2533解题报告。后来在网上看到说LIS问题有O(nlogn)的算法，于是拿来小研究了一下。

这个算法其实已经不是DP了，有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。本来有N个数要处理是O(n)，每次计算要查找N次还是O(n)，一共就是O(n^2)；现在搜索换成了O(logn)的二分搜索，总的复杂度就变为O(nlogn)了。

这个算法的具体操作如下(by RyanWang):

开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。 最长序列长度即为栈的大小top。

这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y]，此时的最长序列长度没有改变但序列Q的''潜力''增大了。

举例：原序列为1，5，8，3，6，7

栈为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。

用该算法完成POJ2533的具体代码如下:

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

纠结DP，从最长上升子序列开始。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

简单模拟，我用DP思想做了一次。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

找规律题

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

简单的数学题

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

暴力枚举

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

貌似我好久没发生活日志了。其实新鲜的东西都发的差不多了，大学生活也进入了一种规律性的重复，就这么日复一日浑浑噩噩地进行下去...

前几天一直在发POJ的解题报告，都是水题，练习C++和STL，结果搞得很多朋友抱怨说到我这看看结果连插嘴的地方都没有...罪过罪过，我的错，今天补上一篇流水账，大家尽情拍砖...(我要审核滴)

唔，各科的期中考试就这么过去了，成绩基本可以无视，反正也占不到多大比例。学校弄期中考试就是为了让大家少挂科，所以...

昨天一觉睡到中午12点，爬起来发现林在写代码，询问之下得知居然是ACM月赛...打开电脑和他一起刷，中午饭也没吃。至下午6点刷了5道题，还差一道最短路径。因为最短路径我就会floyd，可是写完之后居然TLE...也对，就求2个点之间的最短距离怎么也不会让我用floyd的...没办法翻出算法导论开始学习Dijkstra，半个小时后敲完了Dijkstra，这回不TLE了，直接WA...纠结之下放下代码跑出去吃了顿饭然后直奔励耘楼参加校会的换届大会，据说是有聘书拿。可是到了现场被告知聘书还没印好...失望之余不免开始惦记那道最短路径，待了3分钟后突然想到了一个BUG，兴奋之下直接逃离大会现场奔回宿舍，改掉BUG之后终于弹出了可爱的AC，此时我已经交了14次...

今天要出门，天气也格外晴朗，第一站依旧是必胜客，最爱超级至尊。只不过必胜客的沙拉越给越少了，以后去珠海的必胜客不点沙拉了...

通常吃完午饭下午的活动都是看电影，这次依旧不例外，刚好有传说中的《2012》可供观赏。电脑特效制作的很好，虽然还不是非常逼真，我怀疑这次有请游戏动画的制作者...恩，电影很明显地美化了美国总统，当然也体现了美国大片惯有的个人英雄主义精神和冒险精神，主角运气(我们一般称之为RP)简直太好了，跟输了秘籍似的...

恩，看完电影就已经差不多5点了，坐车返校。中午吃了那么多，晚饭可以省了。回来叫Jet去OK便利吃那个鱼丸和豆腐，因为上次在那里吃到的辣椒酱很爽...吃完之后跑去海飞超市看有没有卖，结果没有找到，于是我又返回OK便利看他的辣椒酱卖不卖，结果意外发现他的货架上居然摆着一瓶"盛记辣椒酱"，很好，买下。

恩，貌似现在吃辣椒不会有副作用了，开始吧...