數學題，開始沒做出來，參考
wesley大神思路才AC的?。。。?！囧。。。。。。。。。。現在，我們來計算a[i]，我們只看兩種情況，你或者留下i個問題走開，得到2^(n-i),或者猜一下，你贏的期望是p*a[i-1],我們期望找到這樣一個點，你走或是不走都無所謂。
我們叫他平衡概率分布點*（有點小疑惑）：
eq = 2^(n-i) / a[i-1]
如果p < eq,你走，如果p > eq,你留下來猜，p當然是在區間[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個題時的期望
posted on 2011-11-09 16:24
ACSeed 閱讀(620)
評論(0) 編輯 收藏 引用