首页 > 代码库 > UVa 10900 (连续概率、递推) So you want to be a 2n-aire?
UVa 10900 (连续概率、递推) So you want to be a 2n-aire?
题意：
初始奖金为1块钱，有n个问题，连续回答对i个问题后，奖金变为2i元。
回答对每道题的概率在t~1之间均匀分布。
听到问题后有两个选择：
- 放弃回答，拿走已得到的奖金
- 回答问题：
- 如果回答正确，奖金加倍
- 如果回答错误，游戏结束，得不到奖金
分析：
d[i]表示答对i题后最大期望奖金，设回答对第i题的概率为p，
则回答第i题的期望奖金 = p × d[i]
考虑上不回答的情况，期望奖金最大值为max{2i-1, p*d[i]}
因为p在t~1均匀分布，所以d[i]等于分段函数max{2i-1, p*d[i]}在这个区间上的积分。
因为一段是常函数，一段是直线，所以积分很好求。
令p0 = max{t, 2i/d[i+1]}
- p < p0，选择不回答，奖金期望为2i
- p ≥ p0，选择回答，奖金期望为(1+p0)/2 * d[i+1]
根据全概率公式，第一种情况的概率为p1 = (p0 - t) / (1 - t)
d[i] = p1*2i + (1-p1)*(1+p0)/2 * d[i+1]
边界d[n] = 2n，答案为d[0]
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 35; 6 double d[maxn]; 7 8 int main() 9 {10 //freopen("in.txt", "r", stdin);11 int n;12 double t;13 while(scanf("%d%lf", &n, &t) == 2 && n)14 {15 d[n] = (1 << n);16 for(int i = n-1; i >= 0; --i)17 {18 double p0 = max(t, (double)(1<<i)/d[i+1]);19 double p1 = (p0-t)/(1-t);20 d[i] = (double)(1<<i)*p1 + (1+p0)/2 * d[i+1] * (1-p1);21 }22 printf("%.3f\n", d[0]);23 }24 25 return 0;26 }
UVa 10900 (连续概率、递推) So you want to be a 2n-aire?
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。