UVA10900 So you want to be a 2n-aire?
So you want to be a 2n-aire?
PDF
在一个电视娱乐节目中,你一开始有1元钱。主持人会问你n个问题,每次你听到问题后有两个选择:一是放弃回答该问题,退出游戏,拿走奖金;二是回答问题。如果回答正确,奖金加倍;如果回答错误,游戏结束,你一分钱也拿不到。如果正确地回答完所有n个问题,你将拿走所有的\(2^n\)元钱,成为\(2^n\)元富翁。当然,回答问题是有风险的。每次听到问题后,你可以立刻估计出答对的概率。由于主持人会随机问问题,你可以认为每个问题的答对概率在t和1之间均匀分布。输入整数n和实数t(1≤n≤30,0≤t≤1),你的任务是求出在最优策略下,拿走的奖金金额的期望值。这里的最优策略是指让奖金的期望值尽量大。
Staginner的题解
《训练指南》P335.
这个题目从一开始思路上就有问题,后来结合别人的解题报告来看,终于明白是怎么回事了,而且也突然发现,貌似我适合冒险但不适合赌博……
我们不妨设a[i]表示正确做完第i道题的收益的期望,显然我们最后要求的就是a[0]咯,但这个先放一放,我们先讨论一下在做第i+1个题目前我们是选择答题呢还是选择放弃呢。
首先,我们可以直观的想到,如果做完i题就退出的话,就可以得到2^i这么多钱。不妨假设答对第i+1个题的概率为p,那么我们自然会想到用p乘以“某个值”表示答题所获得的收益的期望,如果p乘以这个值大于2^i的话,我们肯定会选择答题咯,因为若是这样答题的话收益的期望是大于不答题的。那么现在问题就来了,这个“某个值”是什么呢?可能的最大值?可能的最小值?还是平均值(或者说是期望)?
如果做个比喻的话,选最大值的就是冒险狂,选最小值的就是胆小鬼,选平均值的就是接受过良好高等教育的ACMer,一开始我就成了冒险狂……
后来想想,也确实只有平均值在统计里面才比较有说服力,因此题目中所谓的plays the best strategy就是按我们上面所说的去决策每次究竟是答题还是不答题。上面我们只是对于p是固定值来讨论的,如果我们对p是任意的去讨论的话,显然不答题的平均收益是不变的,因为它和p没关系,仍是2^i,如果答题的话平均收益就应该是(ep+1)/2a[i+1],ep就是我们前面讨论的“分水岭”,用表达式写出来就是ep=2^i/a[i+1],当p>ep,那么pa[i+1]>2^i,也就是说如果答对这个题我就可以获得a[i+1]这么多钱,再乘答对的概率p就是答第i+1题的收益的期望,如果这个期望大于2^i,那么就会选择答题。当然题目中让算的是总收益,我们再各自乘以答题与否这些情况出现的概率即可,即a[i]=(ep-t)/(1-t)2^i+(t-ep)/(1-t)(ep+1)/2*a[i+1],这个式子值列出了ep>t的情况,对于ep<=t的情况,也可以类似写出表达式。
现在我们就发现了,计算a[i]是需要用到a[i+1]的,那我们怎么办?倒着算呗。那么a[N]是多少?显然是2^N,因为答对第N个题之后收益的期望自然就是最大的收益。
时间复杂度\(O(n)\)
#include<bits/stdc++.h>
#define il inline
#define co const
template<class T>T read(){
T data=0,w=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-') w=-w;
for(;isdigit(ch);ch=getchar()) data=data*10+ch-'0';
return data*w;
}
template<class T>il T read(T&x) {return x=read<T>();}
typedef long long LL;
co int N=35;
double d[N];
int main(){
int n;
double t;
while(scanf("%d%lf",&n,&t)==2&&n){
d[n]=1<<n;
for(int i=n-1;i>=0;--i){
double p0=(double)(1<<i)/d[i+1];
if(p0<t) p0=t;
double p1=(p0-t)/(1-t);
d[i]=(double)(1<<i)*p1+(1+p0)/2*d[i+1]*(1-p1);
}
printf("%.3lf\n",d[0]);
}
return 0;
}
最新文章
- 1130mysql explain中的type列含义和extra列的含义
- [已解决] github merge指定commit
- jquery无缝间歇向上滚动(间断滚动)
- ASP.NET MVC简单编程之(二)经典路由篇
- new tips
- 线段相交 POJ 2653
- 剑指Offer:互为变位词
- 2016年7款最流行的Java框架
- startActivityForResult相关的
- 用CSS3 做的星体
- Linux系统上的命令使用方法
- 各种异常 及异常类和Object类
- JavaScript—对象创建方式
- 吴恩达课后作业学习1-week4-homework-two-hidden-layer -1
- js怎么将 base64转换成图片
- CMake 示例
- C#中关于@的用法
- Prometheus Node_exporter 之 Network Sockstat
- SQL Server 镜像证书过期处理
- 【MVC】知识笔记