[ACM ] ACM 481 What goes up
ACM 481 What Goes Up
題目 http://203.64.52.212/~ACM/q481.htm
這題解法很明顯的是求LIS
我的想法是用O(n^2)的DP去求LIS
再trcae DPTable找出最後出現LIS
之後看了一下 LuckyCat 的提示是用 LIS with n*log(n)
但是題目有要求
"如果有不止一個最長的嚴格遞增子序列，請輸出在輸入中最後出現的。
例如在 1, 3, 2, 2, 4, 0 中，應該輸出 1, 2, 4 而不是 1, 3, 4。"
n*log(n)的演算法要怎麼做到這個要求?
--
My programs lack own soul......
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.244.132.1
推
05/21 10:34, , 1F
05/21 10:34, 1F
推
05/21 12:09, , 2F
05/21 12:09, 2F
可是 O(nlogn)的演算法要怎麼輸出LIS
O(nlogn)演算法http://src.wtgstudio.com/?rRlcof
像 5,2,3,1,4 的LIS是 2,3,4 可是用O(nlogn)的DPTable最後會變成 1,3,4
不過或許是還有什麼地方我沒想到吧
※ 編輯: netsphere 來自: 60.244.132.1 (05/21 12:53)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
