SP1026 FAVDICE - Favorite Dice

也许更好的阅读体验
\(\mathcal{Description}\)
一个\(n\)面的骰子，求期望掷几次能使得每一面都被掷到
输入有\(T\)组数据，每次输入一个\(n\)
输出保留两位小数

\(\mathcal{Solution}\)
设\(f[i]\)表示已经掷到过\(i\)面，还 期望掷多少次骰子使每一面都被掷到
现在掷一次骰子，有两种情况

1. 有\(\frac{i}{n}\)的概率掷到已经掷到过的面，此时仍然还要掷\(f[i]\)次骰子
2. 有\(\frac{n-i}{n}\)的概率掷到没掷到过的面，此后就掷到过\(i+1\)个面了，还需掷\(f[i+1]\)次骰子

需要注意的是，无论是掷到以上哪种情况，都需要掷一次骰子
所以有
\(f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1\)
将其化简
\(f[i]=f[i+1]+\frac{n}{n-i}\)

\(\mathcal{Code}\)

/*******************************
Author:Morning_Glory
LANG:C++
Created Time:2019年07月21日 星期日 14时51分18秒
*******************************/
#include <cstdio>
#include <fstream>
using namespace std;
const int maxn = 1005;
//{{{cin
struct IO{
    template<typename T>
    IO & operator>>(T&res){
        res=0;
        bool flag=false;
        char ch;
        while((ch=getchar())>'9'||ch<'0')    flag|=ch=='-';
        while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
        if (flag)    res=~res+1;
        return *this;
    }
}cin;
//}}}
int T,n;
double f[maxn];//f[i] -> 有了i个面，变成拥有n个面的期望
int main()
{
    freopen("p1026.in","r",stdin);
    freopen("p1026.out","w",stdout);
    cin>>T;
    while (T--){
        cin>>n;
        f[n]=0;
        for (int i=n-1;i>=0;--i)    f[i]=f[i+1]+1.0*n/(n-i);
        printf("%.2lf\n",f[0]);
    }
    return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧

SP1026 FAVDICE - Favorite Dice

原文：https://www.cnblogs.com/Morning-Glory/p/11221534.html