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

回复  vvnesaa
差不多明白你的意思了，不过有点小问题，你说对于每个i，都把符合条件的x插进去，那如果有 ...
darksteel 发表于 2011-4-20 01:28

恩。。。之前那个没有特别说清楚
对于做DP的顺序：按start从小到大排序，如果start一样，那么按end从小到大排序，如果start和end都一样，只保留cost最大的
下面的话是多余的。。。不需要用堆


对于插入堆的顺序：按end从小到大排序，如果end一样，那么按start从小到大排序，这里start和end都一样大的，和DP顺序一样处理

于是你说的那个(1, 10000)中间有若干比如(50, 10050)(100, 10100)...直到出现一个(10010, 10020)才会把seg 1塞到堆里，因为之前那些(50, 10050)(100, 10100) segs一定不会用到(1, 10000)的结果，因为他们重叠，
所以你的那个例子，只有处理到最后一个seg时，才会真正有值(比如seg1)塞到heap里

其实你写一写，或者跑个例子，很简单的

回复 11# vvnesaa
不知道是不是可以这样理解MM的意思:
1.sort by star;t
2.for i in 1-n
        for j in 1-i such that end[j] < start
             insert dp[j] into heap
        dp[i][i] = value[i][i] + heap.top()
新手上路, 天性愚笨, 望大家多多指教[/i][/i]

回复 11# vvnesaa
哦，刚才我还是有点误解了你的意思，现在应该是理解对了。我再看看

另: 我的解法, 不知道对不对, 烦请大家指教
sort the nodes 1-n by END
dp[0] = 0
END[0] = -INF
for every node i in 1-n, consider two cases   
    a. i is not in the optimized solution, dp = dp[i - 1]
    b. i is in the optimized solution:
        FIND the nearest j before i such that END[j] < START[i]
        dp[i] = value[i] + dp[j]
    assert(dp[i] > dp[i - 1])//assuming all values are positive

the FIND operation on a sorted array cost O(lgn) time(like binary search), other operations are O(1)
thus, total cost = O(n * lgn)[/i][/i][/i][/i]

回复 14# Imbalism

你的find不仅仅要保证可行性，还要保证最优哦～
所以BST的话，没有办法在log n时间把可行和最优都找到吧 :)

回复  vvnesaa
不知道是不是可以这样理解MM的意思:
1.sort by star;t
2.for i in 1-n
        for j i ...
Imbalism 发表于 2011-4-20 09:41

好像就是这样。。。
但是如果这样实现，就是n^2的了。。。
所以直接拿个变量在放heap的那个sorted array那儿指一指，扫一扫，就ok了@@

回复 11# vvnesaa
现在我的理解是，假如现在算的是dp[i](i)，那就把所有已经算出来的结果之中（1<=j<i)，满足j.end <= i.start的dp[j]插入堆，不知是否正确？但插入堆的顺序是按end从小到大排序这个是怎么操作呢？因为插入堆的只能是已经计算过的，但两种排序方式元素可能是交错的，如何才能保证正确性？
[/i]

对的～
那个插入顺序。。。
你这么想：
[1, 5], [2, 3]算好了，现在要算[4, 6]
那么按end从小到大排，[2, 3]就可以塞进heap了。。。
而[1,5]虽然最开始就算好了，但是在这里[4, 6]的时候，还用不上，要用上[1,5]的时候一定是 [a,b], a>5, b>5，那肯定是在[4, 6]后面算的。。。

唉。。。我觉得我没讲清楚。。。给个例子。。。

DP顺序：[1, 5] [2, 3], [4, 6] [6, 10]
入堆顺序：[2, 3] [1, 5] [4, 6] [6, 10]

首先算[1, 5] => 算之前发现入堆顺序的第一个[2, 3], 不满足 3<=1([1, 5].start), 没有元素入heap => done
算[2, 3] => 算之前发现入堆顺序的第一个[2, 3], 不满足 3<=2([2, 3].start), 没有元素入heap => done
算[4, 6] => 算之前发现入堆顺序的第一个[2, 3], 满足 3<=4([4, 6].start), 入heap => done
算[6, 10] => 算之前发现入堆顺序的第二个[1, 5], 满足 5<=6([6, 10].start), 入heap；
                 算之前发现入堆顺序的第三个[4, 6], 满足 6<=6([6, 10].start), 入heap；
                 算之前发现入堆顺序的第四个[6, 10], 不满足 10<=6([6, 10].start), 不入heap； => done

understand?

回复 18# vvnesaa
后来我自己倒是想明白了一点，你看理解的对不对：
需要两个堆，一个是维护end的h1，还一个是维护最优值的h2。每算完一个dp(i)，就把类似（i.end,i)的一个东西插入到h1。而计算dp(i)之前，就把当前h1中从顶上开始，不断把满足j.end<i.start的的dp(j)插入h2，然后删除这个元素。这些堆的插入删除都是logn的，然后可以O(1)从h2中获得对于当前i最优的dp(j)。
这样感觉似乎是对的。如果不用两个堆的话，应该很难维护end从小到大吧？不知这样理解是否正确？

   

回复 19# darksteel

我觉得你的理解是对的
堆其实就是完成了排序嘛～
随便找个排序算法排序就好了 :)