※ 引述《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
真神奇 原來可以這樣子來降低時間複雜度
我了解了 謝謝你 :)
另外再請教一件事情
我在討論版看到有人宣稱他使用了 union-find 來縮短時間 解決這一題
如果真是這樣 那要怎麼做呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.167.19.57