作者sa072686 (小紅)
看板b97902HW
標題Re: [情報] 剛彈十四........
時間Sat Dec 20 21:50:21 2008
嗯的確不太簡單，不過可以用 BFS 變形一下，用類似 DP 的手法來合併狀態…
以下假設大家都會 BFS。
原先 BFS 通常只拿來找出最小步數解，因為深度小的必定會先走到，
所以重覆的狀態都不會去走它。例如：走迷宮的話，一樣在位置 (3, 2)，
在 BFS 中先踩到那格的情形一定是最佳的。通常第二次找到位置 (3, 2)
就不丟進佇列。這裡有可能有兩種解，步數都是最短，但都經過 (3, 2)
且踩上去時的步數不一樣。但步數一樣、踩在一樣格子上的情形仍能視為相同，
故於 BFS 中改記狀態 state[n][m][r] 代表走了 r 步，人數 n 機器數 m，
那麼擴張時如果狀態 p 可轉到狀態 q，就把狀態 p 可能的方法數加到狀態 q 去。
例如人數 (3, 1) (0, 0) 和人數 (2, 1) (1, 0) 一樣都可以轉到 (1, 1) (2, 0)
設此三個狀態分別為 p, q, r 則 ways(r) = ways(p) + ways(q)
所以相同的狀態可以一次轉過去，在狀態重覆性大時會節省相當多時間。
但相對耗記憶體，不過當走到步數 n 時，只需擴展出步數 n+1 而用不到所有 < n 的，
所以原本要開 [人數][機器數][步數]，可以改成開 [人數][機器數][2]。
大致可以用這樣的方法來節省時間…好發公關大人的測資全跑完大概也不用一秒。
※ 引述《purplebleed (紫熠)》之銘言：
: 這次剛彈真的還蠻不簡單的
: 暴蒐法條件要設好
: 可是
: 如果條件設太嚴檢查會錯
: (少次數....)
: 如果太寬又會超時
: 而且這次測資都不簡單壓
: 隨便暴蒐都有機會破萬步以上
: 所以
: 要讓程式又快又會正確(好像強人所難...........)
: (BFS可以解啦....不過要變化一下.....其實我也不是很清楚.....)
: 遞迴確定可以AC......雖然遞迴慢.....
: 附上一些測資&&測資答案好了......
: (當然是自己出的........)
: 20 1 15 2 5 1 Min: 11 Ways: 2312
: 150 1 150 0 3 1 Min: 151 Ways: 11399
: 100 1 0 0 3 1 Min: 101 Ways: 5098
: 8 6 0 0 6 1 Min: 9 Ways: 376
: 20 0 20 0 3 1 Min: 19 Ways: 19
: 7 5 0 0 3 1 Min: 17 Ways: 1
: 這些都要在兩秒內跑完比較正常
: 不要像我一樣把批改娘當DEUBG機
: (沒辦法嘛~~TLE不試試怎知XD)
: 結果上傳超多次的............
: 大家加油!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
1F：推 purplebleed:的確不用一秒....可適用遞迴的話就不知了......... 12/20 22:47
2F：推 LoganChien:除了第二組，我的也不用一秒。第二組 10 ~ 15 秒。 12/20 22:59
3F：→ LoganChien:顯然 O(lg N) 比 O(Const) 弱太多了。 12/20 23:00
4F：→ LoganChien:有空來改寫好了。 12/20 23:01
5F：推 godgunman:爲什麼要 O(logN) @@? 12/21 09:28
6F：→ sa072686:第二組我的不用半秒，但會頓一下… 12/21 20:14
7F：→ sa072686:總之我是把重點放在狀態合併，這點比DFS好很多 12/21 20:15