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)的做法，不过还没想到如何用在这个例子上
若有错请大家帮忙指正