Re: [情報] 剛彈十四........

[sa072686 (小紅)]

嗯的確不太簡單，不過可以用 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
推 purplebleed:的確不用一秒....可適用遞迴的話就不知了.........
推 LoganChien:除了第二組，我的也不用一秒。第二組 10 ~ 15 秒。
→ LoganChien:顯然 O(lg N) 比 O(Const)  弱太多了。
→ LoganChien:有空來改寫好了。
推 godgunman:爲什麼要 O(logN) @@?
→ sa072686:第二組我的不用半秒，但會頓一下…
→ sa072686:總之我是把重點放在狀態合併，這點比DFS好很多