※ 引述《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