Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

O(n)不知道怎么弄的?倒是还有另一个O(nlogn)的方法的,正确的

Posted by ArXoR at 2005-10-26 22:30:35 on Problem 2519
In Reply To:那么是不错的随机算法了。哈哈 Posted by:zhucheng at 2005-10-26 22:28:54

Followed by:

How to do? (0) zhucheng 2005-10-26 22:31:30
- 这个需要类似dp地做一下 (0) frkstyc 2005-10-26 22:32:57
  - 你是说在左端维护凸包的时候吗？ (0) zhucheng 2005-10-26 22:35:00
    - yes (0) frkstyc 2005-10-26 22:40:13
- 那个是基于原子段的合并,原子段是那些段中任意分割点左边平均值小于等于右边平均值的段....云云 (0) ArXoR 2005-10-26 22:41:13
  - 有点KMP的味道 (0) zymx 2005-10-26 22:43:11
    - 形象 (0) frkstyc 2005-10-26 22:43:38
  - 用convex hull来理解会容易些吧 (0) frkstyc 2005-10-26 22:44:22
    - 没错....开始那个看得我云里雾里的,现在还是有点... (0) ArXoR 2005-10-26 22:45:37
Ｏ（ｎ）就是直接线性的扫描一下就可以了……　ZhouY的论文讲的很清楚 (0) fz 2005-10-27 14:25:54
- where? (0) xreborner 2005-10-27 15:19:05
- 不维护标准凸包的左边，直接删除不可能增大目标值的点？ (0) zymx 2005-10-27 18:57:07
  - 长度有上下界的话求总和最大才有O(n)吧？ (0) frkstyc 2005-10-27 19:00:18

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator