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