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

那样啊！不过我都找不到反例，似乎是对的吧。

Posted by zhucheng at 2005-10-26 22:26:50 on Problem 2519
In Reply To:我们那样....-___- Posted by:ArXoR at 2005-10-26 22:25:15

Followed by:

有反例的，我自己生成随机测试数据，错误率约在1/5000 (0) zymx 2005-10-26 22:28:00
- 那么是不错的随机算法了。哈哈 (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