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

欢迎提供更多更强的数据。

Posted by xiedi at 2007-02-17 18:47:17 on Problem 2576
In Reply To:难道这题过的人这么多,原来数据水成这样…… Posted by:rovingcloud at 2007-02-17 00:54:01
> 由于过的人实在太多,心想可能不是DP这么复杂,就用随机化恶搞了一下(就只是单纯地交换),居然过了……
> 然后用另外一种错误的算法来写,前面的DISCUSS也有朋友提到,就是每次寻找可以使得绝对值变小的一对数进行交换,直到找不到这样的数对为止。这样的算法只能保证较优解,下面这个数据是过不了的:
> 8
> 3 7 7 10 40 70 70 99
> 用上述方法得出的是152 154 ,但是正确应该为153 153
> DP才是正道……不过我估计写DP的反而时间会更慢 -,-
> 所以后来还是在上述错误的算法基础上再加一个随机,也就是当找不到更优的数对时,随机交换两个元素,再调整到局部最优。这样的随机才是经典的随机 ^_^
> 此题不应沦为水题啊~~~

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