SPOJ Favorite Dice(概率dp)

题意：

一个骰子，n个面，摇到每一个面的概率都一样。问你把每一个面都摇到至少一次需要摇多少次，求摇的期望次数

题解：

dp[i]：已经摇到i个面，还需要摇多少次才能摇到n个面的摇骰子的期望次数

因为我们只知道dp[n]的值，所以我们只能倒推，dp[n]=0（感觉大部分概率dp都是倒推~~~~）

dp[i]=i/n*dp[i]+(n-i)/ndp[i+1]+1

化简一下：

dp[i]=dp[i+1]+n/(n-i)

代码：

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

using namespace std;

const int maxn=1e3+10;

double dp[maxn];

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        double n;

        memset(dp,0,sizeof(dp));

        scanf("%lf",&n);

        dp[int(n)]=0.0;

        for(int i=n-1;i>=0;--i)

        {

            dp[i]=dp[i+1]+n/(n-i);

        }

        printf("%.2lf\n",dp[0]);

    }

    return 0;

}

巴特西

SPOJ Favorite Dice(概率dp)

最新文章

热门文章