ZJU/ZOJ 1076 Gene Assembly 解题报告

题目大意是给出n条基因链的起点和终点，选取最多的基因链，使其起点和终点不相交并输出选取方案。

DP或贪心都是O(n)的时间复杂度，但贪心的空间复杂度更低。DP的做法是用f[i]表示按终点递增排序后，选取到终点第i大的基因链时最多可选的基因链，用seg[i]表示经过排序后的第i条基因链，则f[i]=max(f[j]+1,f[i-1])(seg[j].r<seg[i].l,1<=j<i<=n);如果f[i]比f[i-1]大则输出第i条基因链的编号。贪心的做法则是按终点递增排序后，不断选取起点比上一选取的基因链大的基因链输出其编号输出即可，其正确性的证明是非常直观的。

3000087 2008-07-23 20:14:13 Accepted 1076 FPC 00:00.00 412K IwfWcf@LZOI