作者sophialiege ()
看板ACMCLUB
标题Re: [问题] 10486 Mountain Village
时间Mon Sep 5 14:14:00 2005
※ 引述《DJWS (...)》之铭言：
: 这一题我想了几天还是想不出来有什麽合适的演算法可以解决他
: 有可能是我脑中记得的演算法太少了
: 所以来问问看这一题要怎麽解决
: 感激不尽 T_T
令[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
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.162.205.7