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 |
难道这题过的人这么多,原来数据水成这样……由于过的人实在太多,心想可能不是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