noip模拟测试18 T2搜索

考试 .....打了个搜索60分

下来改了个字母A了,,,,,

考试后n个小时当我得知别人的搜索思路后,开始造数据看看自己跑的快不快然后

答案错了????

考试数据真水骗分骗到A。。。

正确搜索思路每次往左右两边最近的未搜点处搜,然后break手玩一下可证明正确性。。。

后来发现各种搜索均被hank(除了alpaca某羊),因为当n比较小时m比较小然后时间巨大,,,,或者说时间直接接近2000 nm稍正常  就跑很长时间。

学来了羊驼的最优性剪枝,,for循环一遍m  找左右两边的点同时记录 ,   然后算出已经超时且未搜的点说明我们已经不可能获得这些权值,,,

用所有精灵权值和减去这些权值代表我们可能到达的最优解,这个东西如果小于ans直接return...各种数据跑的飞快。。。。。。。。

原文地址:https://www.cnblogs.com/three-D/p/11343594.html