雖然我不知道為什麼很多人都把它寫成 最小路覆蓋,不過我是寫 二維LIS。

二維LIS,就是先照 x 排序,然後再對 y 做LIS。

這題已經幫你排好 x 了,不過題目是要求 最長遞減子序列,所以我把 y 反過來賦值,就可以直接用 LIS。

用 二分搜 能夠到 O(nlgn)。

我的code

http://codepad.org/p3yM3KKh

 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()