【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，显然没用欧拉级数化简，化简后就过了。

 #include <cstdio>

 #include <cmath>

 #define MAXN 100000

 double a[MAXN];

 int main() {

     int n;

     int i;

     double ans;

     a[] = ;

     for (i=; i<MAXN; ++i)

         a[i] = a[i-]+1.0/i;

     while (scanf("%d", &n) != EOF) {

         if (n < MAXN) {

             ans = a[n];

         } else {

             ans = log(n*1.0)+0.57721566490153286060651209;

         }

         printf("%.4lf\n", ans);

     }

     return ;

 }

巴特西

【HDOJ】4986 Little Pony and Alohomora Part I

最新文章

热门文章