2008年7月26日星期六

ZJU/ZOJ 2319 Beautiful People 解题报告

题目大意是求两个关键字严格递增的最长不降序列。

做法和ZJU/ZOJ 1108类似,也是先对一个关键字排序,然后对第二关键字进行DP。不过由于n<=100000所以O(n^2)的DP是肯定会TLE的,只能用O(nlogn)的做法,具体参见ZJU/ZOJ 1108 解题报告。但很奇怪的是如果预处理排序时两个关键字都按降序排序就会WA,第二关键字改成升序就AC了……

3007513 2008-07-26 21:25:55 Accepted 2319 FPC 00:02.26 2368K IwfWcf@LZOI

6 条评论:

相关文章

 
Creative Commons License
除非另有声明,本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。