首页 > 代码库 > 【HDOJ】4986 Little Pony and Alohomora Part I
【HDOJ】4986 Little Pony and Alohomora Part I
递推。设n个盒子的Spell次数为S(n),期望为E(n)。
当有n个盒子时,可能第n把钥匙在第n个盒子中,此时的Spell次数应该为(n-1)!+S(n-1);
当第n把钥匙不在第n个盒子中,混合排列,此时的Spell次数为(n-1)*S(n-1),
因此,期望E(n) = S(n)/n!,S(n) = (n-1)!+S(n-1) + (n-1)*S(n-1) = (n-1)!+n*S(n-1),
则E(n) = S(n-1)/(n-1)! + 1/n = E(n-1) + 1/n。
因此,得到递推公式E(n) = 1+1/2+1/3...1/n。
调和计数,第一次交TLE,显然没用欧拉级数化简,化简后就过了。
1 #include <cstdio> 2 #include <cmath> 3 4 #define MAXN 100000 5 6 double a[MAXN]; 7 8 int main() { 9 int n;10 int i;11 double ans;12 13 a[0] = 0;14 for (i=1; i<MAXN; ++i)15 a[i] = a[i-1]+1.0/i;16 17 while (scanf("%d", &n) != EOF) {18 if (n < MAXN) {19 ans = a[n];20 } else {21 ans = log(n*1.0)+0.57721566490153286060651209;22 }23 printf("%.4lf\n", ans);24 }25 26 return 0;27 }
【HDOJ】4986 Little Pony and Alohomora Part I
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。