850 AlvinZH的学霸养成记III
思路
难题。概率DP。
第一种思考方式：直接DP
dp[i]：从已经有i个学霸到所有人变成学霸的期望。
那么答案为dp[1]，需要从后往前逆推。对于某一天，有可能会增加一个学霸or不增加。
①增加：\((dp[i+1] + 1) * P\)
②不增加：\((dp[i] + 1) * (1-P)\)
其中，\(P = i * (n - i) * p / (C(n,2))\)，C(n,2) = (n - 1) * n / 2。其含义是：n个人中选出一非学霸一学霸的方法数/n个人中选出两人方法数。
状态转移方程：\(dp[i] = (dp[i + 1] + 1) * P + (dp[i] + 1) * (1 - P)\)。移项化简后可得： \(dp[i] = dp[i + 1] + 1 / P\) 。
其实可能正着想更简单，令dp[i]表示达到班内有i个学霸的期望天数。则有dp[1] = 0。相同的分析分发，最后依然可以得到 \(dp2[i] = dp[i-1] + 1/P\) 。最后答案为dp[n]。
优化一下，完全不需要这个dp数组，使用一个变量累加即可得到答案。
第二种思考方式：期望叠加
每天至多有一个人转化为学霸，考虑第i个人转化为学霸的期望天数D[i]，那么所有人转化为学霸的期望天数 \(ans=D[1]+D[2]+…+D[n-1]\)。
设第i个人转化为学霸的概率为p[i]，则第i个人转化为学霸服从几何分布。
：在n次伯努利试验中，试验k次才得到第一次成功的机率。详细地说，是：前k-1次皆失败，第k次成功的概率。
期望\(EX=1*a+2*(1-a)*a+3*(1-a)^2*a+...\) ，错位相减求和即可得期望为 \(1/p[i]\)。
故 \(D[i]=1/p[i]\) ，而 \(p[i]=p*i*(n-i)/(n*(n-1)/2)\)，所以 \(D[i]=n*(n-1)/(2*p*i*(n-i))\) ，那么我们就可以在O(n)的时间内得到ans值.
你可能已经发现，最后二者计算方法其实一模一样的，侧面证明答案正确。
分析
两种方法时间复杂度都为O(n)。
需要注意的问题是乘法溢出问题，在计算 \(n*(n-1) / (2*p*i*(n-i))\) 的过程中，有两个地方会溢出，一个是n(n-1)，你可以通过(double)n(n-1)防止溢出，注意(double)(n(n-1))没有效果；第二个溢出是2i(n-i)p，你可以把p放前面先计算或者把i强制转换为浮点数防止溢出。
参考资料：
参考代码一
//// Created by AlvinZH on 2017/9/15.// Copyright (c) AlvinZH. All rights reserved.//#include#include #include #define MaxSize 100005double dp[MaxSize];//dp[i]表示学霸数量为i时，到达目标的期望int main(){ int T, n; double p, ans1, ans2, p1; scanf("%d", &T); while (T--) { scanf("%d%lf", &n, &p); dp[n] = 0; for (int i = n-1; i > 0; i--) { ans1 = (double)i * (n-i);//选出一非学霸和一学霸 ans2 = (double)n * (n-1) / 2;//从n个人中选两个人 p1 = ans1 / ans2 * p; dp[i] = dp[i+1] + 1.0/p1; } printf("%.3lf\n",dp[1]); } return 0;}
参考代码二
//// Created by AlvinZH on 2017/9/15.// Copyright (c) AlvinZH. All rights reserved.//#includeint main(){ int T, n; double p, ans; scanf("%d", &T); while (T--) { scanf("%d %lf", &n, &p); ans = 0.0; for(int i = 1; i < n; i++) ans += 1.0 * n* (n-1) / (2 * p * i * (n-i)); printf("%.3lf\n", ans); } return 0;}