※ 引述《babufong (嗶嗶)》之銘言： : 371. Licence plates : http://projecteuler.net/problem=371 : 俄勒岡州的車牌號碼是由三個英文字母後面接著三位數字(0到9)所組成的。 : Seth 開車去上班時，他會玩一個小遊戲： : 每當他在路途上，看到兩個車牌號碼的數字部分相加為 1000 時，就算勝了這場遊戲。 : (如 MIC-012 和 HAN-988，或是 RYU-500 和 SET-500，這都算勝利，只要是在同一趟 : 車程中看到。） : 計算出 Seth 贏得遊戲所需要看到的車牌數的期望值，並將答案給到小數點後八位數。 一開始往馬可夫鏈的方面去想，結果被困了好久 最後靈光一閃，發現了其實只是個簡單的DP題 車牌英文字母不重要, 因為對每一個數字來說，每一種3位英文字母出現的機率相等 所以問題簡化成只有數字相加 要加成1000, 一共有1+999, 2+998, 3+997, ...., 499+501, 500+500；500種配對 500比較特殊，要另外討論，所以是499個數字配對和跟有沒有500 DP的狀態是500*2 表示499對數字中,有幾對已經在「聽牌狀態」了，跟有沒有500數字在其中，所以是500*2 已出現的數字是{2,3,499}跟{7, 23, 888}沒有不同，在DP上，都是屬同一個狀態 皆是表示有3對數字在「聽牌狀態」 「聽牌狀態」是我發明的辭，表示一個數對已有其中之一被看到， 在等待另一個數字湊成1000 接下來是求取每一次看見車牌，還無法湊成1000的機率 假設在第n次看見車牌後，還無法湊成1000的機率為p_n(註: 用 _ 表示下標) 很顯然的 在前一次尚未湊成1000，而在這次湊成1000的機率為(1-p_n)-(1-p_(n-1))=p_(n-1)-p_n 期望值為 sigma(2<=n=∞) (p_(n-1)-p_n)*n 很直覺的，p_1=1 p_2以後就用DP算出 差不多算到第300次看見車牌，p_n就衰減到近乎於零 所以算到300次即可 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.62.203.103 ※ 編輯: utomaya 來自: 61.62.203.103 (02/13 09:45)