Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:您给讲一下?

Posted by frkstyc at 2005-04-18 18:33:24 on Problem 2018
In Reply To:您给讲一下? Posted by:TN at 2005-04-18 18:04:43
这个题原始的O(N^2)必然tle,看见100000这么大规模就知道他必然要暗算这种解法了。即使发现了所求的序列最长必定不会超过2F-1,O(NF)的算法也难保不会被一堆F=50000,N=100000的数据搞死。所以肯定要找O(NlogN)或者O(NlogF)级的算法。我现在是没这个能耐去设计这种算法啦,所以就上网去找了一篇paper,到portal.acm.org搜一下maximum average subsequence应该就可以找到了。

今天下午我问了uni这个怎么做,他说的好像是蒙可能的平均值,用最大子段和代替最大子段平均,在蒙的基础上用二分来修正。至于怎么用凸包来做就不知道了,今天我写了一个类似Quick Hull的办法也是tle。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


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