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 ArXoR at 2005-10-26 22:25:15 on Problem 2519
In Reply To:怎么cheat呢？ Posted by:zhucheng at 2005-10-26 22:24:20

Followed by:

那样啊！不过我都找不到反例，似乎是对的吧。 (0) zhucheng 2005-10-26 22:26:50
- 有反例的，我自己生成随机测试数据，错误率约在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