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)的做法，不過還沒想到如何用在這個例子上
若有錯請大家幫忙指正