作者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/cn.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