SP1026 FAVDICE - Favorite Dice(扔筛子期望)

题目链接

很老套的期望了

定义$dp[i]$为已经有$i$面筛子扔过,还需要仍到$n$面的期望

那么$dp[n]=0$

$p=\frac{i}{n}$表示此时扔到已有的面的概率

$dp[i]=(dp[i]+1)?p+(dp[i+1]+1)?(1?p)$

$意思是有p的概率从i面转移到i面,有(1?p)的概率转移到dp[i+1]$

把右边的$dp[i]$移项到左边即可

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int t,n;
double dp[maxn];
int main()
{cin >> t;while( t-- ){cin >> n;dp[n]=0;for(int i=n-1;i>=0;i--){double p=i*1.0/n;dp[i]=( dp[i+1]+1 )*(1-p)+p;dp[i]/=(1-p);}printf("%.2lf\n",dp[0]);}
}