查看: 5384|回复: 33
收起左侧

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

  |只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:Ananimous(1) C++找bug
下一篇:Microsoft(2) 找出第k大的数
danielgao 2011-4-19 12:53:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (86)
 
 
3% (3)    👎
本帖最后由 danielgao 于 2011-4-19 13:04 编辑

回复 1# wwwyhx


n^2的DP? d(i)表示选了第i个到第n个之间所能取到的最大值.
回复

使用道具 举报

vvnesaa 2011-4-19 19:42:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (38)
 
 
0% (0)    👎
本帖最后由 vvnesaa 于 2011-4-20 11:50 编辑

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


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

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

回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-4-19 20:53:33 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

vvnesaa 2011-4-19 21:15:58 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (38)
 
 
0% (0)    👎
回复 4# wwwyhx

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

使用道具 举报

darksteel 2011-4-19 22:27:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
可以优化到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)到一时没想明白,能具体解释下吗?
回复

使用道具 举报

vvnesaa 2011-4-19 23:27:27 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (38)
 
 
0% (0)    👎
本帖最后由 vvnesaa 于 2011-4-20 11:52 编辑

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)

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

使用道具 举报

Imbalism 2011-4-19 23:38:07 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (42)
 
 
0% (0)    👎
首先显然有:如果最优选择中选择了 i 和 j,不妨设:j.start < j.end < i.start < i.end

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

heap是按item的value排序的吗??
回复

使用道具 举报

vvnesaa 2011-4-20 00:07:47 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (38)
 
 
0% (0)    👎
heap是按item的value排序的吗??
Imbalism 发表于 2011-4-19 23:38


nope,塞进去的是dp[item]
回复

使用道具 举报

darksteel 2011-4-20 01:28:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
回复 7# vvnesaa
差不多明白你的意思了,不过有点小问题,你说对于每个i,都把符合条件的x插进去,那如果有的x对于当前i不符合条件,但对于之后的某个i符合了,怎么操作才能不漏掉它?
举例来说,假如第一个segment就是(1,10000,100000000),中间有若干个segment都是开始于10000之前的,所以计算他们的时候segment[1]都不会被插入,但最后一个segment开始于100001,那我们怎么操作才能回头把segment[1]插入进来呢?

   
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表