Ananimous(2) 找出得分最高的无重复子段

我把题目和大家的评论都看了想了。感觉DP思路大家都能想到，只是在寻找前一个衔接点的时候做法不一样。
楼主提到的直接用for循环从后往前遍历，，效率是O(N^N)，通常情况下已经够用了。MM的算法我看了半天不是很明白。喜欢Imbalism提出的二分，简单明了，效率稳定。

我把题目和大家的评论都看了想了。感觉DP思路大家都能想到，只是在寻找前一个衔接点的时候做法不一样。
楼主提到的直接用for循环从后往前遍历，，效率是O(N^N)，通常情况下已经够用了。MM的算法我看了半天不是很明白。喜欢Imbalism提出的二分，简单明了，效率稳定。
ljfljf2006 发表于 2011-4-24 11:56

    对，如果直接一个个向后查找效率在重合情况严重的情况下会很低，同意用二分，虽然实现复杂点但是效果更稳定

DP么？
按照时间点从前往后update一个数组dp


对于每个point n来说，有两种可能性
1.没有以这个point作为finish point的segment，那么这个点最大的score和等于前一个点，即dp[n]=dp[n-1]，因为没有别的可能性了
2.如果有以这个点作为finish point的segment（{m,s,n}），那么这个点最大的socre在dp[n-1],dp[m]+s里选一个最大的



不晓得对不对........

回复 33# benny
差不多就是这样，这个题我一直关注的比较多，目前总结有如下结论：
如果按end对所有segment进行排序，那dp的时候对每个i需要找到满足seg[m].end<=seg.start的那个最大m，这个可以用二分，所以复杂度是O(nlogn)。
那个MM的方法是按start对segment排序，然后dp的过程中以end作为key维护一个堆，堆里的元素是dp[0..i-1]，然后对于每个i从堆里弹出end<=seg.start的所有符合条件的元素，取最大的那个作为当前选择。由于每个元素进堆一次，因此复杂度也是O(nlogn)。两个方法都是很好的。