為什麼這篇Zerojudge PTT鄉民發文收入到精華區：因為在Zerojudge PTT這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者KitWoolsey (貓)看板C_and_CPP標題[問題] zerojudge的一題,自己測...
遇到的問題(Question)：
http://zerojudge.tw/ShowProblem?problemid=d822
餵入的資料(Input)：
希望的正確結果(Expected Output)：
跑出來的錯誤結果(Wrong Output)：
本題目共 4 個測試點，您沒有通過任何一個測試點。(score:0)
錯誤訊息如下：
*** 第 1 點 (30%)：WA (line:1)
您的答案為: 0
正確答案為: 561121
*** 第 2 點 (30%)：WA (line:1)
您的答案為: 232000
正確答案為: 769683
*** 第 3 點 (30%)：WA (line:1)
您的答案為: 396800
正確答案為: 903126
*** 第 4 點 (10%)：WA (line:1)
您的答案為: 11152
正確答案為: 4522
開發平台(Platform)： (例: VC++, Gcc, OpenGL, Linux, ...)
C++
程式碼(Code)： (請善用置底文標色功能)
http://nopaste.csie.org/99636
我是用累加法 如果偵測到該格是障礙物 那該格的累積走法當然是0
否則就等於該格(上方+左方)的總走法 如此這樣一直從左上先往右 在往下 依序累加到右下
把最下面的三行comment//去掉 就可以看到 每一個點的累積情形
不知道我錯在哪裡呢@@"
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.30.182
→ tkcn:你是不是有些x,y看反了? (noy-1)*m+nox <= 這不合理 12/10 23:54
→ KitWoolsey:我看看@@ 12/10 23:54
→ KitWoolsey:真的耶 改完之後 0分變10分= = 12/11 00:01
→ KitWoolsey:好奇怪噢 只過10%的測資 怎會這樣XD 12/11 00:04
http://nopaste.csie.org/2d6e0
新版 我發現他的x跟y給的順序跟我想像中的反過來XD
所以吃xy的時候我反過來吃 再改ik那邊的順序
※ 編輯: KitWoolsey 來自: 61.228.30.182 (12/11 00:14)
→ bleed1979:N是y方向，M是x方向，(x,y)實際是給(y,x)。 12/11 01:35
http://nopaste.csie.org/2d6e0這是已經改過的版本,可是只拿的到10%的那個測資,不知道為什麼呢@@?
※ 編輯: KitWoolsey 來自: 61.228.25.109 (12/11 12:33)
推 Yshuan:你的dp陣列currentrow應該做二維 我體會不到你遞迴式的意義 12/11 14:19
以範例來說的話
一開始 array currentrow是長這樣
0 1 0 0 0 0 ...
跑了 i=1的
currentrow[k]= (currentrow[k]+currentrow[k-1])%mod; 之後
會變成
(第一排) 0 1 1 1 1 1 .......
然後在做i=2的時候 就會開始把上一排的數值抓過來之後洗掉:
(第一排) 0 1 1 1 1 1 .......
v v v v v
(第二排) 0->1->0->1->2->3 .......
|
|
(障礙物,那格是0
接下來,在做第三排的時候,第一排的數據已經完全用不到了...
所以我覺得應該不用一直保留前面的數據..
我只需要知道 這排(overwrite後) 和 上一排(overwrite前)的數據
補上範例的 currentrow 全部變化過程
0 1 1 1 1 1
0 1 0 1 2 3 黃色的三格是障礙物
0 1 1 0 2 0
0 1 2 2 4 4 <-----做了四排之後,最後的currentrow[m]就是要求的答案(4)
※ 編輯: KitWoolsey 來自: 61.228.28.202 (12/11 14:31)
推 Yshuan:看懂了xd" 我沒用一維寫過~ ~ 12/11 14:35
→ x000032001:原PO想說的應該是滾動array 12/11 14:39
→ bleed1979:sort(store,store+index); 現在ZJ好像上不去？？ 12/11 16:46
→ bleed1979:另外你要考慮點重複給的問題，需要loop找下一index。 12/11 16:49
→ KitWoolsey:那時候t跟index不是一樣0.0"? 12/11 17:22
→ bleed1979:對，是一樣的，請忽略。測試重複給點的部分就可以了。 12/11 20:35
→ KitWoolsey:過了過了> " < 感謝各位大大.. 12/13 19:16