HDU 4405 Aeroplane chess (概率dp)

OJ题目：click here ~~

大概题意：飞行棋，N + 1格，标为0---N ， M个地方可以连飞。掷一个六面筛子，掷到几就飞几步 。现在0处 ， 问飞到N 需要掷筛子的次数的期望。

这里有一遍好文：点我就到~

看完上面这篇文章，状态转移就很好想了。

dp[ i ] 为 从 i 格处飞到 N 还需要掷筛子的次数的期望。显然dp[ N ] = 0 , dp[ 0 ] 即为要求的结果。

dp[ i ] = 1/6 * dp[ i + 1] +  1/6 * dp[ i + 2] +  1/6 * dp[ i + 3] +  1/6 * dp[ i + 4] +  1/6 * dp[ i + 5] +  1/6 * dp[ i + 6]  + 1;

当然如果dp[ i  + j] 中 i + j  > N 则不加。

AC_CODE

double dp[100010];
int f[100010];
int main()
{
    int n , m;
    while(scanf("%d%d",&n,&m))
    {
        if(n == 0&&m == 0) break;
        int i , j , a, b;
        memset(dp , 0 , sizeof(dp));
        memset(f , -1 , sizeof(f));
        for(i = 1;i <= m;i++)
        {
            scanf("%d%d",&a,&b);
            f[a] = b;
        }
        dp[n] = 0;
        for(i = n - 1;i >= 0;i--)
        {
            if(f[i] != -1) dp[i] = dp[f[i]];
            else
            {
                for(j = 1;j <= 6;j++)
                {
                    if(i + j > n)
                        break;
                    else
                    {
                        dp[i] += (1.0/6)*dp[i+j];
                    }
                }
                dp[i] += 1.0;
            }
        }
        printf("%.4lf\n",dp[0]);
    }
    return 0;
}