› 看板 C_and_CPP 關於我們 聯絡資訊
作者netsphere ()
看板C_and_CPP
標題[ACM ] ACM 481 What goes up
時間Thu May 21 08:52:05 2009
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
推 gba356:倒過來做！ 05/21 10:34
推 chrisdar: 一語道破 XD 05/21 12:09
可是 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)