sgu495：概率dp / 推公式

概率题。。可以dp也可以推公式

抽象出来的题目大意：

有 n个小球，有放回的取m次问被取出来过的小球的个数的期望

dp维护两个状态第 i 次取出的是没有被取出来过的小球的概率dp[i] 和取出的是已经被取出来过的小球的概率np[i];

如果第 i-1 次取出的是已经被取出来过的小球那么第 i 次取出没有取出来过小球的概率即为 dp[i-1]；

反之则为 dp[i-1] - 1/n（没有取出来过的小球少了一个）

所以可以得到状态转移方程 dp[i]=dp[i-1]*(dp[i-1]-1/n)+np[i-1]*dp[i-1];

还可以推公式。。不过我还是觉得推公式得靠人品，能yy出来那当然是极好的。。。

代码：

#include <iostream>

#include <stdio.h>

#include<string.h>

#include<algorithm>

#include<string>

#include<math.h>

#include<ctype.h>

using namespace std;

#define MAXN 10000

int n,m;

double dp[];

double np[];

double solve()

{

    double res=;

    memset(dp,,sizeof(dp));

    memset(np,,sizeof(np));

    dp[]=;

    np[]=;

    for(int i=;i<=m;i++)

    {

        dp[i]=dp[i-]*(dp[i-]-1.0/(double)n)+np[i-]*dp[i-];

        np[i]=-dp[i];

    }

    for(int i=;i<=m;i++)

    {

        res+=dp[i];

    }

    return res;

}

int main()

{

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        printf("%.10lf\n",solve());

    }

    return ;

}

公式。。

#include <stdio.h>

#include<math.h>

double n,m;

int main()

{

    while(scanf("%lf%lf",&n,&m)!=EOF)

    {

        printf("%.10lf\n",n-n*pow(((n-)/n),m));

    }

    return ;

}

巴特西

sgu495：概率dp / 推公式

最新文章

热门文章