PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 基於排序的greedy

看板Prob_Solve (計算數學 Problem Solving)作者johnathan717 (好神公仔)時間10年前 (2014/04/03 17:16)推噓0(0推 0噓 2→)

留言2則, 1人參與討論串1/1

1. 直覺想到的作法是，把每個k-tuple當成圖上的點如果一個點覆蓋另一個點，就連一條有向邊，會產生一個DAG 生成圖需要O(k*n^2) 最後對DAG求longest path即可例如先做topological sort，需要O(V+E) = O(n^2) 再做DP，也是O(n^2) 所以整體是O(k*n^2) 2. 想想之後上一篇板友推的從LIS(Longest Increasing Subsequence)去做更簡潔可以像上一篇有說到的先對第一維排序，之後假設他們是x1, x2, ..., xn 然後令dp[i] = 以xi為末項的最長覆蓋序列長度就可以列出關係式 dp[1] = 1, dp[i] = 1 + max{ dp[j] | j < i, xj被xi覆蓋 } 這樣子對n個k-tuple也是O(k*n^2) 如果不只要長度還要把整個序列求出來，那dp除了存長度還要存他的前一項也就是要另加一個prev[i]是以xi為末項的最長覆蓋序列的倒數第二項 prev[i] = -1(沒有前一項隨便令)，prev[i] = argmax{dp[j] | j < i, xi覆蓋xj} 雖然說LIS是有O(nlogn)的做法，不過還沒想到如何用在這個例子上若有錯請大家幫忙指正 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.79.239.190 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1396516617.A.A15.html