四 08
这是一个二维的LIS问题，先把第一维排序离散化，把第二维的值存到线性表A中。接下来就是求路径划分了，根据Dilworth定理，最长反链长度等于最小链划分数，所以只需求最长下降序列长度。
由于数值范围有限，可以用计数排序+基数排序，求LIS用二分查找，时间复杂度为O(NlogN)。
另外也可以直接用最小路径覆盖解决。
Read the rest of this entry »
订阅
22 queries. 0.424 seconds.
Designed by NattyWP .
Images by desEXign.
Recent Comments