题目大意是给出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
博文
是nlogn吧,dp不是n^2或nlogn吗?
回复删除DP和贪心都只是线性扫一次，所以是O(n)的
回复删除可能你和下午跟我聊天的某个访客一样都把这题当最长不降序列了？其实这是会议安排问题的典型模型，排序如果用线性的排序则总的时间复杂度也是O(n)的
回复删除toms outlet, http://www.tomsoutlet-stores.com/
回复删除nike roshe, http://www.nikerosherunshoes.co.uk/
prada handbags, http://www.pradahandbagsoutlet.co.uk/
soccer jerseys, http://www.cheapsoccerjersey.net/
michael kors outlet store, http://www.michaelkorsoutlet-store.us.com/
true religion jeans, http://www.truereligionjeansoutlets.us.com/
oakley sunglasses, http://www.oakleysunglasses-outlet.us.com/
nike free 5, http://www.nikefree5.us/
louis vuitton bags, http://www.louisvuittonbag.us.com/
chanel handbags, http://www.chanelhandbags-outlet.co.uk/
chanel handbags, http://www.chanelhandbags-outlet.us.com/
louis vuitton handbags, http://www.louisvuittonhandbag.us/
louis vuitton outlet, http://www.louisvuittonoutlet.in.net/
ghd hair straighteners, http://www.ghdhairstraightenerssale.co.uk/
nba jerseys, http://www.nbajerseys.us.com/
coach outlet, http://www.coachoutletstores.com.co/
true religion jeans, http://www.truereligionjeanscanada.com/
swarovski crystal, http://www.swarovskicrystals.co.uk/
mbt shoes, http://www.mbtshoesoutlet.us.com/
michael kors handbags, http://www.michaelkorshandbags.in.net/
chanel handbags, http://www.chanelhandbagsoutlet.in.net/
michael kors outlet online, http://www.michaelkorsoutletonline.in.net/
polo ralph lauren, http://www.poloralphlauren.us.org/
the north face clearance, http://www.thenorthfaceclearances.us.com/
jordan shoes, http://www.jordan-shoes.us.com/
beats by dr dre, http://www.beatsbydrdre-headphones.us.com/
the north face uk, http://www.thenorthfaces.org.uk/
1003maoqiuyun
zhengjx20160520
回复删除vans sneakers
kobe shoes
ray ban sunglasses uk
louis vuitton purses
ghd hair straighteners
toms wedges
ralph lauren outlet
coach outlet
coach factory outlet online
longchamp le pliage
ray ban outlet
michael kors outlet clearance
nike air max uk
oakley vault
tory burch boots
christian louboutin sale clearance
abercrombie outlet
coach outlet
louis vuitton outlet online
adidas originals store
gucci handbags
nhl jerseys
supra for sale
air max
coach factory outlet online
cheap air jordans
louis vuitton outlet
juicy couture
jordan retro 13
hollister clothing
christian louboutin shoes
oakley sunglasses
louis vuitton purses
adidas uk
gucci bags
michael kors outlet
asics running shoes
adidas running shoes
hollister clothing
coach outlet online
ralph lauren polo shirts
回复删除polo ralph lauren
ugg boots
ralph lauren polo
michael kors handbags
chaussures christian louboutin
michael kors outlet online
air max 90
north face jackets
cheap ugg boots
201612.26chenjinyan
polo ralph lauren
回复删除coach outlet
nike outlet store
ralph lauren outlet
ferragamo outlet
discount oakley sunglasses
coach outlet online
cheap ray ban sunglasses