Robert Anderson's Blog

非常單純的一題SSSP

http://nopaste.csie.org/a9fc0

N進位轉換

但是有負號

這是比較有趣的一點

另外注意N == 0的情況

利用DFS + Heuristic Function

作法有點類似IDA*

不過沒有Iterative Deepening

另外真的有無解的情況

不要相信謠言阿= =

他其實要字典最小順序

但我用BFS解這問題

其實有一個簡單的方法解決這個問題

一樣用BFS去解這個問題 大體都不用改

可是你的enqueue順序是用

蠻簡單的

可以發現只需要以有牛的pasture為起點即可

然後看他可以到哪些pasture 到達的地點cnt就加一

到最後檢查哪些地點的cnt剛好等於牛數

這樣時間複雜度是O( K * (N + E) )

沒有記錯的話這是UVA ACM一樣的題目

但是USACO有一樣的題目

而且範圍比較大

這題我是用當初USACO那題的作法

所以快很多(茶

只需要求該點往所有點的最短距離

再找其他點過來的最短距離

這樣只需要做一次SSSP 然後反邊再做一次SSSP即可

這樣時間複雜度只有O(N + E)

動態規劃要O(N^2)

不會過

想一下就會發現其實是很簡單的排序加貪婪法

時間複雜度O(NlogN)

蠻有趣的題目

作法蠻簡單的

我自己是用

N-2做回來

假設現在作到i

利用數學歸納解

然後排出Pascal三角形去做解答

不過一開始自己發明一個table 就一直WA=    =

最後還是改回pascal triangle