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

//Given a collection of segments, each segment have three values, the beginning point, the end point and the
//score. Find a set of segments have the largest score but non of them is overlapped with others.

{start point, end point, score}
比如{1,3,3}, {2,4,5}, {3,5,3}
答案是{1,3,3}，{3,5,3}，

回复 1# wwwyhx


n^2的DP？ d(i)[i][i][i]表示选了第i个到第n个之间所能取到的最大值.[/i][/i][/i]

回复  wwwyhx
n^2的DP？ d(i)表示选了第i个到第n个之间所能取到的最大值.
danielgao 发表于 2011-4-19 12:53

UPDATE:
偶太二了太二了太傻了太傻了 >_<
不需要用堆。。。只记下当前可能的最大值就可以了。。。

********************
可以优化到O(n log n)
按开始时间排序做DP
按结束时间排序，一边做DP，一边按这个顺序往堆里插
每次DP的选择都是从堆里O(1)求的

可以优化到O(n log n)
按开始时间排序做DP
按结束时间排序，一边做DP，一边按这个顺序往堆里插
每次 ...
vvnesaa 发表于 2011-4-19 19:42

   

MM too 厉害了

回复 4# wwwyhx

害羞@@
有的是GG告诉我的>_<
我最近也在复习这些～～
加油多出点题哦 ^_^

可以优化到O(n log n)
按开始时间排序做DP
按结束时间排序，一边做DP，一边按这个顺序往堆里插
每次 ...
vvnesaa 发表于 2011-4-19 19:42

O(n^2)的dp大概是这样：

1.         for(int i = 1; i <= n; i++)
   
2.                 dp[i] = -INF;
   
3.         dp[0] = 0;
   
4.         for(int i = 1; i <= n; i++)
   
5.                 for(int j = 0; j < i; j++)
   
6.                         if(seg[i].start >= seg[j].end)
   
7.                                 dp[i] = max(dp[i], dp[j]+seg[i].score);

复制代码

其中seg是按开始时间和结束时间排过序的。

你说的优化到O(nlogn)到一时没想明白，能具体解释下吗？

O(n^2)的dp大概是这样：

其中seg是按开始时间和结束时间排过序的。

你说的优化到O(nlogn)到一时没 ...
darksteel 发表于 2011-4-19 22:27

首先显然有：如果最优选择中选择了 i 和 j，不妨设：j.start < j.end < i.start < i.end

我们按start从小到大排序
如果我们要算：如果1.. i 中选择了 i ，当前最优cost是多少，
那么一定是一堆x，都满足x.start < x.end < i.start < i.end，并且在这些x中选择cost最大的

所以用heap，每次算完一个i，就把已经算出来的满足 x.end < i.start 的item塞到heap里
每次要算 i 的时候，就在拿heap.top出来算

每个item只会进heap一次，所以heap cost = O(n log n)
DP每次选择是O(1)的
所以总的cost是O(n log n)

不知道我说清楚没有@@
但愿我没错@@

首先显然有：如果最优选择中选择了 i 和 j，不妨设：j.start < j.end < i.start < i.end

我们按star ...
vvnesaa 发表于 2011-4-19 23:27

heap是按item的value排序的吗？？

heap是按item的value排序的吗？？
Imbalism 发表于 2011-4-19 23:38

nope，塞进去的是dp[item]

回复 7# vvnesaa
差不多明白你的意思了，不过有点小问题，你说对于每个i，都把符合条件的x插进去，那如果有的x对于当前i不符合条件，但对于之后的某个i符合了，怎么操作才能不漏掉它？
举例来说，假如第一个segment就是(1，10000，100000000)，中间有若干个segment都是开始于10000之前的，所以计算他们的时候segment[1]都不会被插入，但最后一个segment开始于100001，那我们怎么操作才能回头把segment[1]插入进来呢？