2008年9月25日星期四

dd_engi的一道题——字典序最小的LIS

这几天基本在学校机房混,看着他们玩DNF(当然我不会),以幸灾乐祸为主。我这几天眼睛状态创造了历史新低,结果有一节政治课我60%的时间是——正襟危坐,面向黑板和老师,毫无表情,双眼紧闭。毕竟是理科班,不用太客气。

前几天看完了《穆斯林的葬礼》。这部作品写得很悲惨,我从来没有被感动到这种程度。心情一连两天处于低潮状态。用书中的一句话,全书也不过是一个字——情。在这里向没有读过的人推荐一下,不会白读的。

\end{nonsense} \begin{point}

此题出自dd_engi同学在2008.9.20 出的一套模拟赛中。我大略看了一下题,觉得这到比较简单,或者说只看懂了这一道题(毕竟它最短啊),开始了思考。此题完全是LIS问题的一个基本变形,可以说会LIS就能做上这道题。我用的LIS是最简单的O(n2)的算法,再添上那个简单变形。比较不巧,程序不在这里,改天发上来。这个算法由于复杂度的原因,只能过5个测试点,学会了O(nlogn)的再改过来。

没有评论: