PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] leetcode 464 can i win

看板Prob_Solve (計算數學 Problem Solving)作者pttworld (批踢踢世界)時間7年前 (2017/05/20 06:39)推噓7(7推 0噓 12→)

留言19則, 4人參與討論串3/4 (看更多)

1. 玩家1和玩家2交替選擇數字。第一次到第三次選擇會是玩家1，玩家2，玩家1。對於第三次選擇的時候，第一次選1，第二次選2和第一次選2，第二次選1，實際上是沒有差別的。使用map紀錄1和2被選的樣態，相同樣態直接取結果對遞迴截枝。 2. 最佳化的判斷，在所有可能有一成立即成立，直接函數返回加速。 AC, 1s https://github.com/jamalch-tw/oj/blob/master/LeetCode/464.cpp ※ 引述《powertodream (The Beginning)》之銘言： : https://leetcode.com/problems/can-i-win/#/description : 是兩個人互相取數字, 當第一個人取的數字超過目標, 就return true : 原本的想法是, player 1 挑全部沒選過的number, 然後呼叫secondPlayerWin的 : function : 去判斷是不是有存在secondPlayer win的, 只要有存在A 選的這個number就是不行的 : 不過寫不太好的吃了個wrong answer, : 偷看看討論串解答 : 看了很多的作法, 都是做類似 : !helper(desiredTotal - i) : 的遞迴, : 想半天仍然不太懂... 有版友有興趣一起研究研究嗎? : 這個是原作者的解釋, 但是我仍然不懂他的意思, 為什麼code要寫成那樣 : ** : The strategy is we try to simulate every possible state. E.g. we let this : player choose any unchosen number at next step and see whether this leads to : a win. If it does, then this player can guarantee a win by choosing this : number. If we find that whatever number s/he chooses, s/he won't win the : game, then we know that s/he is guarantee to lose given such a state. : // try every unchosen number as next step : for(int i=1; i<used.length; i++){ : if(!used[i]){ : used[i] = true; : // check whether this lead to a win, which means : helper(desiredTotal-i) must return false (the other player lose) : if(!helper(desiredTotal-i)){ : map.put(key, true); : used[i] = false; : return true; : } : used[i] = false; : } : } : map.put(key, false); -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.43.36.13 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1495233549.A.DC9.html

推

powertodream

05/21 02:51, , 1^F

05/21 02:51, 1^F

→

powertodream

05/21 02:51, , 2^F

05/21 02:51, 2^F

推

powertodream

05/21 02:54, , 3^F

05/21 02:54, 3^F

題目規定雙方皆為最佳玩法，思路必須相對：如果a找到最佳，b就輸了；如果b找到最佳，a就輸了。有找到就返回是考慮全部的提速。 ※ 編輯: pttworld (115.43.36.13), 05/21/2017 16:38:42