UVA11427 Expect the Expected 概率dp+全概率公式

时间:2024-09-20 14:38:02

题目传送门

题意:小明每晚都玩游戏,每一盘赢的概率都是p,如果第一盘就赢了,那么就去睡觉,第二天继续玩;否则继续玩,玩到赢的比例大于p才去睡;如果一直玩了n盘还没完成,就再也不玩了;问他玩游戏天数的期望;

思路:由于每次玩游戏,每天玩游戏都是独立重复试验,所以可以考虑一天玩游戏,玩不到p的概率(p都玩不到?)。

  设$dp[i][j]$表示玩了i次游戏,获胜j次,并且过程中期望都不会超过p的概率。

  则显然有:$dp[i][j]=dp[i-1][j]*(1-p)+dp[i-1][j-1]*p$。

   需要注意的是,我们必须保证过程中游戏分数的期望不会超过p,所以每一个状态都必须是$\frac{j}{i}<p$,而且由于是T组样例,记得每次都要清空dp数组,否则上一次的答案可能会影响当前这次(上一次不合法的状态到了这一次变成合法状态了,被统计入了答案)。

  然后求出总的失败概率,设概率为q,期望天数为e。

  由全概率公式可得$e=q*1+(1-q)*(e+1)$

  移项得$e=\frac {1}{q}$

#pragma GCC optimize (2)
#pragma G++ optimize (2)
#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dep(i,b,a) for(int i=b;i>=a;--i)
#define clr(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pii pair<int,int >
using namespace std;
typedef long long ll;
ll rd()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int maxn=;
double dp[maxn][maxn];
int x,y,n;
int main(){
int T,cat=;
cin>>T;
while(T--){
scanf("%d/%d%d",&x,&y,&n);
double p=(double)x/y;
clr(dp,);
dp[][]=;
rep(i,,n){
for(int j=;j*y<=i*x;j++){
dp[i][j]=dp[i-][j]*(-p);
if(j)dp[i][j]+=dp[i-][j-]*p;
}
}
double res=;
for(int i=;i*y<=n*x;i++){
res+=dp[(int)n][i];
}
printf("Case #%d: %d\n",cat++,(int)(/res));
}
}