數(shù)學(xué)題,開始沒做出來,參考
wesley大神思路才AC的?。。。?!囧。。。。。。。。。。現(xiàn)在,我們來計(jì)算a[i],我們只看兩種情況,你或者留下i個(gè)問題走開,得到2^(n-i),或者猜一下,你贏的期望是p*a[i-1],我們期望找到這樣一個(gè)點(diǎn),你走或是不走都無所謂。
我們叫他平衡概率分布點(diǎn)*(有點(diǎn)小疑惑):
eq = 2^(n-i) / a[i-1]
如果p < eq,你走,如果p > eq,你留下來猜,p當(dāng)然是在區(qū)間[t,1],所以如果eq < t你總是留下來猜,
然后把他們加起來,這里有兩種情形:
如果eq < t:
a[i] = (1 + t) / 2 * a[i - 1];
如果t < eq < 1:
a[i] = (((eq - t) / (1 - t)) * 2 ^ (n - i)) + (((1 - eq) / (1 - t)) * ((1 + eq) / 2) * a[i - 1])
a[n] 就是答案;
a[i] 表示你還剩i個(gè)題時(shí)的期望
posted on 2011-11-09 16:24
ACSeed 閱讀(607)
評(píng)論(0) 編輯 收藏 引用