astar 月赛第一题 Fir

Problem Description

小H是一个程序员。但是他很喜欢一些新奇的东西。

有一次，他去找物理实验室的朋友玩。他见到了一串非常有意思的粒子。N个粒子排成一排。每一秒中，每一段连续的粒子中会随意有一个爆炸，爆炸后该粒子就消失了，且将原来连续的一段粒子分隔成两段。

小H希望知道所有粒子都爆炸完的期望时间。

Input

         第一行为一个整数T（1 <= T<= 400），表示有T组测试数据；

         每组数据一个正整数N（1<=N<=400），表示一开始的粒子数。

Output

         对于每组数据，输出期望时间（秒）。保留五位小数。

Sample Input

3

1

2

3

Sample Output

1.00000

2.00000

2.66667

Sample Cl.

对N=3，若第一个爆炸的粒子在旁边，则还需两秒；若第一个爆炸的在中间，则再过一秒即可。故答案为2/3*3+1/3*2=8/3。

代码

#include <stdio.h>

#define  MAX 401

float fun(float *f,int n) //n个球爆炸的耗时
{
    int j=0;
    float sum =0;
    float factor = 1.0/(float)n;
    for(j=1;j<=n;j++)
    {
        // 在第j个爆炸情况
        //分别考虑j之前j-1个所需的时间和之后的n-j个爆炸时间，个数多的期望时间大
        if((j-1)> (n-j))
        {
            if(f[j-1]>=0.0)
            {
                sum = sum + f[j-1] +1;             
            }
           else 
           {
                sum= sum + fun(f,j-1) +1 ;           

           }
        
        }
        else//n-j大
        {
            if(f[n-j]>=0.0)
            {
                 sum = sum + f[n-j] +1; 
            }
            else
            {
                sum= sum + fun(f,n-j) +1 ;     
            }
        }
        
    }
    f[n] = factor*sum ;//存储局部解，以便后续直接获取而不必递归
    return f[n];
}
int main()
{
    
    int t;
    int n;
    int j;
    scanf("%d",&t); 
    float f[MAX];
    while (t--)
    {
        scanf("%d",&n);        
        for (j=0;j<=n;j++)
        {
            f[j] = -1;
        }
        f[0]=0;
        f[1]=1;
        printf("%.5f\n",fun(f,n));    
        
    }
    return 0;
}

astar 月赛 第一题 Fir

astar 月赛第一题 Fir