作者johnathan717 (好神公仔)
看板Prob_Solve
標題Re: [問題] 基於排序的greedy
時間Thu Apr 3 17:16:55 2014
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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1396516617.A.A15.html
1F：→ johnathan717:其實對任一維sort都等於1的某種topological sort 04/03 17:19
2F：→ johnathan717:2的DP其實也跟longest path沒兩樣，兩做法根本一樣XD 04/03 17:20