期望dp_牛客博客

我真是个nc啊~

这么简单的概率,居然想了几分钟???

$首先很容易看出第i次取球后会有2+i个球存在$

白球和黑球没有本质上的区别,所以各占一半

$\color{Red}但是啊,用期望怎么来写??$

定义 $dp[i]$ 为取 $i$ 次球后剩下白球个数的期望

$dp[i]可以从dp[i-1]转移而来$

$若上一次抽到白球,概率是\frac{dp[i-1]}{i-1+2},此时贡献是dp[i-1]+1个白球$

$若没有抽到白球,概率是上面的补集,贡献是dp[i-1]个白球$

所以贡献乘概率相加就算期望了

而且这题正推逆推都无所谓了

#include <bits/stdc++.h>
using namespace std;
int n;
double dp[1000009];
int main()
{
    cin >> n;
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        double p= dp[i-1]/(i-1+2 );
        dp[i]=dp[i-1]*(1-p)+p*(dp[i-1]+1);
    }
    printf("%.7lf",dp[n]);
}