作者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