UVA 11427 (概率DP+期望)

题目链接http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=35396

题目大意:每晚打游戏。每晚中,赢一局概率p,最多玩n局,如果最后不能保证胜率大于p,则从此不玩。问打游戏的天数的期望。

解题思路

首先分析每天晚上的。

设f[i][j]为前i天,已经赢j局的概率。

由全概率公式,那么当天晚上完蛋的概率q=f[n][0]+f[n][1]+.....f[n][终止条件].

至于为什么从完蛋(输)的角度考虑,主要是由于n局的条件存在,最多n局很容易解,而n局中赢局的最大递推范围,就是0~( j/i<=a*i)

若从当晚不完蛋的角度考虑,则赢局的范围不好确定。

最后每天晚上完蛋概率q=f[n][0~n],(后面没推是0,所以这里偷懒取n就行)

打游戏的天数问题,是个离散型期望问题。

X 1 2 3 4 5
P Q Q(1-Q) Q*(1-Q)^2 Q*(1-Q)^3 Q*(1-Q)^4
EX 1*Q 2*Q(1-Q) 3*Q*(1-Q)^2 4*Q*(1-Q)^3 5*Q*(1-Q)^4

则EX=Q+2*Q(1-Q)+3*Q*(1-Q)^2+.....

是个无穷级数,不好求和。

对这个数列进行变形:设x=EX/Q,则x=1+2(1-Q)+3*(1-Q)^2+..., ①

则(1-Q)x=(1-Q)+2*(1-Q)^2+... ②

①-②=EX=Qx=1+(1-Q)+(1-Q)^2+.... ,设1-Q=K

对这个等比数列求和,EX=lim (1-K^n)/(1-K)=1/(1-K)=1/Q。

还有一种奇葩的思考方式,设最后期望为e。

设事件A为第一天完蛋。那么P(A=1):Q,期望是1。P(A=0):1-Q,期望e+1,e=Q+(1-Q)*(e+1),e=1/Q.

至于为什么第一天不完蛋则期望是e+1。(=。=暂时没想出来)

#include "cstdio"
#include "cstring"
#define maxn 105
double f[maxn][maxn];
int main()
{
//freopen("in.txt","r",stdin);
int T,n,a,b,no=;
double p;
scanf("%d",&T);
while(T--)
{
memset(f,,sizeof(f));
scanf("%d/%d%d",&a,&b,&n);
p=(double)a/b;
f[][]=;f[][]=;
for(int i=;i<=n;i++)
for(int j=;j*b<=a*i;j++)
{
if(!j) f[i][j]=f[i-][j]*(-p);
else f[i][j]=f[i-][j]*(-p)+f[i-][j-]*p;
}
double q=;
for(int i=;i<=n;i++) q+=f[n][i];
printf("Case #%d: %d\n",++no,int(/q));
}
}
3333670
Accepted
  29 623
2015-02-09 23:33:29
上一篇:css实现强制不换行/自动换行/强制换行


下一篇:“你什么意思”之基于RNN的语义槽填充(Pytorch实现)