LightOJ 1248 Dice (III) 機率DP

Dice (III) LightOJ - 1248

扔一個 n n n 面篩子，問要看到每一個面至少一次需要扔的期望數。

設 d p [ i ] dp[i] dp[i] 為已經扔了 i i i 個面的期望值，則 d p [ n ] = 0 dp[n]=0 dp[n]=0，有：

d p [ i ] = 1 + i n d p [ i ] + n − i n d p [ i + 1 ] d p [ i ] = n n − i + d p [ i + 1 ] \begin{aligned} dp[i]&=1+\frac{i}{n}dp[i]+\frac{n-i}{n}dp[i+1]\\ dp[i]&=\frac{n}{n-i}+dp[i+1] \end{aligned} dp[i]dp[i]​=1+ni​dp[i]+nn−i​dp[i+1]=n−in​+dp[i+1]​

代碼如下（期望倒推）：

#include<iostream>
#include<cstdio>
//#define WINE
#define MAXN 100010
using namespace std;
int T,iCase,n;
double dp[MAXN];
int main(){
#ifdef WINE
    freopen("data.in","r",stdin);
#endif
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        dp[n]=0;
        for(int i=n-1;i>=0;i--)
            dp[i]=dp[i+1]+1.0*n/(n-i);
        printf("Case %d: %.8lf\n",++iCase,dp[0]);
    }
    return 0;
}