【LightOJ - 1248 Dice (III)】概率期望DP

LightOJ - 1248 Dice (III)

题意

给你一个n面的均匀的骰子，问期望摇多少次可以看到所有的面。

做法

首先我们设dp[i]为当前看到不同的i面，可以看到所有面的期望次数，很显然dp[n]=0
之后我们可以根据概率得到转移方程

$dp[i]=(\frac{n?i}{n}?(dp[i+1]+1))+\frac{i}{n}?(dp[i]+1)$’

方程的意义为：当前看到i个不同的面，有$\frac{n?i}{n}$的几率看到一个没看过的面，之后的期望就是$dp[i+1]$的期望，有$\frac{i}{n}$的几率看到一个已经看过得面，期望就是$dp[i]$，之后直接化简得到：

$dp[i]=dp[i+1]+1+\frac{i}{n?i}$

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 1e5+5;
double dp[maxn];
int main()
{
    int t;scanf("%d",&t);int cas=0;while(t--){
    int n;scanf("%d",&n);memset(dp,0,sizeof(dp));for(int i=n-1;i>=0;i--){
    dp[i]=dp[i+1]+1+1.0*i/(n-i);}printf("Case %d: %.12f\n",++cas,dp[0]);}return 0;
}