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

有反例的，我自己生成随机测试数据，错误率约在1/5000

Posted by zymx at 2005-10-26 22:28:00 on Problem 2519
In Reply To:那样啊！不过我都找不到反例，似乎是对的吧。 Posted by:zhucheng at 2005-10-26 22:26:50

Followed by:

那么是不错的随机算法了。哈哈 (0) zhucheng 2005-10-26 22:28:54
- O(n)不知道怎么弄的?倒是还有另一个O(nlogn)的方法的,正确的 (0) ArXoR 2005-10-26 22:30:35
  - 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
你是不是删掉最左点后，只把他的下一个点加入？ (0) zhucheng 2005-10-26 22:31:08
- 最后交的程序在这样做之前加了个判断，确保正确解不丢失，然后再只加相邻点。 (0) zymx 2005-10-26 22:34:04

Post your reply here:

Home Page Go Back To top