※ 引述《sophialiege ()》之铭言： : 令[u,v]是正解 : 就是最佳解的最低处高度是u,v是最高处 : 因为每个格子的值在0~99之间,所以u和v也是在这之间 : 对於每一组假设的[u,v],你可以在图上将高度介於这之间的位置做记号 : 看连通的记号足不足够盖一个部落 : 再来是要降复杂度,假如[u,v]足够盖,那麽[u,v+k] (k 是正整数) : 也一定足够 ==> bisch is possible : 故复杂度粗估是 Constant * 100 * 8 * 40 * 40 : ^^^ ^^^ ^^^^^^^ : u log(v) graph search 我想到了一个有趣的方法 因为u和v相差越小越好, 於是可以这麽做: 令u和v一开始为0 若是[u,v]小於给定值, 便将v加上一, 让连通的地方增加 若是[u,v]大於给定值, 则让u加上一, 让连通的地方减少 当u v两人害羞的追来追去的时候, 纪录所有符合条件的[u,v], 最後印出最小的v-u即可 这样是对的吗? :p -- Edit: 已经验证结果确实是正确的 :) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.122.26.149 ※ 编辑: DJWS 来自: 140.122.26.149 (09/10 22:03)