SDUT 飞行棋 (概率DP & 期望)

飞行棋

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

飞行棋是在一个长度为n的棋盘上走动棋子的游戏。游戏开始时有一个棋子在棋盘的开始，位置是1。然后每一步玩家掷一次骰子，并将棋子往前跳骰子正面大小个格子。

当棋子跳出飞行棋的棋盘时游戏结束。问游戏结束时玩游戏的人掷骰子次数的期望。

输入

 第一行输入一个数T代表测试用例组数（T<=200），接下来T组测试用例，每组测试数据为棋盘大小。

输出

对于每个棋盘，输出玩家要掷骰子次数的期望(结果保留到小数点后4位)。每行输出一个结果。

示例输入

2
1
2

示例输出

1.0000
1.1667

提示

 

来源

 

示例程序

 

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

double dp[1010];

int main(){

    //freopen("input.txt","r",stdin);

    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        dp[1]=1;
        dp[2]=1.0/6*dp[1]+1;
        dp[3]=1.0/6*(dp[1]+dp[2])+1;
        dp[4]=1.0/6*(dp[1]+dp[2]+dp[3])+1;
        dp[5]=1.0/6*(dp[1]+dp[2]+dp[3]+dp[4])+1;
        dp[6]=1.0/6*(dp[1]+dp[2]+dp[3]+dp[4]+dp[5])+1;
        for(int i=7;i<=n;i++)
            dp[i]=1.0/6*(dp[i-6]+dp[i-5]+dp[i-4]+dp[i-3]+dp[i-2]+dp[i-1])+1;
        printf("%.4lf\n",dp[n]);
    }
    return 0;
}