Re: [ACM ] ACM 481 What goes up
1.陣列開到100000就可以了
2.用binary search來達到nlgn, 傳回的是low或mid
3.另用一個陣列紀錄index, 從後面倒回來查找
AC程式碼：http://src.wtgstudio.com/?zmsWcb
因為趕完成時間沒有特別注重語法, 速度應可更快
Bleed
※ 引述《netsphere ()》之銘言：
: 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)的演算法要怎麼做到這個要求?
--
World of bleed1979
http://bleed1979.myweb.hinet.net/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.16.70
推
05/21 17:24, , 1F
05/21 17:24, 1F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
