[ACM ] 825 Walking on the Safe Side

看板C_and_CPP作者時間15年前 (2010/07/05 21:55), 編輯推噓0(0推 0噓 31→)
留言31則, 3人參與, 最新討論串1/1
題目:http://zerojudge.tw/ShowProblem?problemid=d198 WA Code:http://nopaste.csie.org/99790 問題: 網路上能找到的測資都對 但上傳就WA了 不知道錯在那裡 Debug兩天了...Orz -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.205.109.7
→
07/05 22:11, , 1F
可能要注意最後一列的輸出
07/05 22:11, 1F
→
07/05 22:13, , 2F
恩 謝謝l大 不過Zerojudge上顯示第一筆測資就錯了 Orz
07/05 22:13, 2F
→
07/05 22:18, , 3F
感覺跑迴圈的地方怪怪...我看不到圖, 不過走的時候應
07/05 22:18, 3F
→
07/05 22:19, , 4F
該是左上到右下, 行列數由小到大吧?
07/05 22:19, 4F
→
07/05 22:20, , 5F
我用的是樓上的方法。
07/05 22:20, 5F
→
07/05 22:21, , 6F
如果是行列遞減, 是不是存的時候也要做點手腳? 例如反
07/05 22:21, 6F
→
07/05 22:21, , 7F
是用bottom-up的DP 所以迴圈是從右下開始
07/05 22:21, 7F
→
07/05 22:21, , 8F
著存
07/05 22:21, 8F
→
07/05 22:22, , 9F
因為你走的方向, 跟你DP出來的值順序是相關的
07/05 22:22, 9F
→
07/05 22:26, , 10F
還是不知道錯在那 Orz
07/05 22:26, 10F
→
07/05 22:28, , 11F
你現在走的方向是「從右下走到左上」, 但是存的地圖卻
07/05 22:28, 11F
→
07/05 22:28, , 12F
是「從左上走到右下」在用的地圖
07/05 22:28, 12F
→
07/05 22:29, , 13F
bottom-up的DP 不就是這樣嗎?
07/05 22:29, 13F
DP[V][B]=DP[V+1][B]+DP[V][B+1] 要先有DP[V+1][B]跟DP[V][B+1] 才能算DP[V][B] 所以要dp迴圈要從右下走到左上 ※ 編輯: netsphere 來自: 123.205.109.7 (07/05 22:31)
→
07/05 22:31, , 14F
地圖存的方式, 使得你一定要用行列遞增的方式來跑迴圈
07/05 22:31, 14F
→
07/05 22:31, , 15F
如果要遞減也是可以, 只是地圖就要「反轉」處理過
07/05 22:31, 15F
→
07/05 22:32, , 16F
現在不是講你DP的問題, 而是資料儲存的方式
07/05 22:32, 16F
→
07/05 22:32, , 17F
我想測資給行列應該是亂序的
07/05 22:32, 17F
→
07/05 22:32, , 18F
儲存方式跟你跑DP的方向沒有配合好
07/05 22:32, 18F
→
07/05 22:34, , 19F
原po的方式一樣可以通過，往右下或往右上都可以。
07/05 22:34, 19F
→
07/05 22:34, , 20F
07/05 22:34, 20F
→
07/05 22:35, , 21F
改好的code，看algorithm的部份就可以了。
07/05 22:35, 21F
→
07/05 22:35, , 22F
打太快了，修正︰1.往右下2.往左上都可以。
07/05 22:35, 22F
→
07/05 22:36, , 23F
不過UVa那邊用int就可以過了，Zero這邊還蠻嚴格的。
07/05 22:36, 23F
→
07/05 22:37, , 24F
兩種方向都能過是因為出來的值會對稱的關係吧?
07/05 22:37, 24F
→
07/05 22:40, , 25F
b大請問一下我的DP漏考慮了什麼?
07/05 22:40, 25F
→
07/05 22:42, , 26F
超出邊界
07/05 22:42, 26F
→
07/05 22:45, , 27F
DP部份沒有錯，錯在char Buff開不夠大。
07/05 22:45, 27F
→
07/05 22:46, , 28F
邊界部份超出為0，所以沒差，把buff改1000原code會過。
07/05 22:46, 28F
→
07/05 22:49, , 29F
喔 我了解了 char[101] 當然不夠 XD 謝謝l大和b大
07/05 22:49, 29F
→
07/05 22:50, , 30F
那是剛好障礙跟其他地方初始化為0的關係...
07/05 22:50, 30F
→
07/05 22:51, , 31F
還是不要依賴全域變數的這種特性, 不然改成區域就炸了
07/05 22:51, 31F
‣ 更多 netsphere 的文章
文章代碼(AID): #1CCUHgz9 (C_and_CPP)