Robert Anderson's Blog

這題要利用到一些數論

因為石頭最多100

那麼中間距離將可以縮減

可是要怎麼縮減呢

利用a b兩數互質 則超過LCM(a, b)皆可被組成

拆解成N = (x - y) * (x^2 + xy + y^2)

a = (x - y)

看起來需要求到N^1/2

實際上只需要到約N^1/3左右即可（可以自行思考）

接著把a = (x - y)代入第二個式子 (x^2 + xy + y^2)

雙向BFS

詳細概念看我該篇說法

http://robertanders.pixnet.net/blog/post/26554434

另外我做Hashtable去存取判重

速度上比較快

原本是想貼之前拿到的講義

不過我實在有點看不太懂裡面在寫啥阿(查)

它寫什麼展開樹 一開始我還想說那是啥

結果應該是生成樹(Spanning Tree)

卡車說的沒錯

是很簡單的XD

而且發現真的跟SPFA幾乎一樣吧

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

假設已經知道起點和終點

而每個情況最大拓展的STATE數量是原本的R倍

則F(n) = R * F(n - 1) where F(0) = 1

那個走N步就可能會產生R^N種情形

如果說從兩邊走同樣步數 我們原本需要搜尋R^L種情況

動態規劃

每年每年去算 取得該年最多拿到多少錢 (只需要求該年最多拿多少錢這樣遞推絕對可以得最佳解)

假設該年你花M元 那你最多得到多少獲利

注意他花費一定是1000的倍數 所以可以縮減情況

再加上複利的部分

時間複雜度是O(N^2 log N)

先切成兩邊

去作個別的sum

這樣就有兩堆N^2的List

接下來sort ( O(N^2 log N) )

暴力解

不過注意是相對位置 所以只需要枚舉後面的移動情況就可以了

因此最多7^6個state

http://nopaste.csie.org/20368

卡特蘭數

假設新加入的點跟另外一個點連起來後

那他就會把點切成兩邊

求兩邊組合數乘積

因此就枚舉所有切的情況