题目链接: 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
|