Aeroplane chess

2 0
8 3
2 4
4 5
7 8
0 0

1.1667
2.3441

题意为一条直线上有N+1个格子，编号0-N，也是其位置，有一枚骰子。比方当前位置你在i，骰子执到了 y点（1<=y<=6），那么下一步你就到了i+y位置，格子里有几个特殊的格子。能够从x位置瞬间转移到y位置，不须要步数，假设转移以后的格子还是特殊的格子，那么继续转移，要求的是，最后到达的位置>=n,所须要的投骰子次数的期望。

我们用 dp[i]表示当前位置到达位置>=n所须要投掷骰子的平均次数。

那么非常明显有 dp[n]=0; 而我们要求的则是dp[0] （起点）

注意两点：

①不遇到特殊格子时，投掷一次筛子，由当前位置i到达位置 ,i+1 , i+2 , i+3 , i+4 , i+5 ,i+6 的概率是一样的。都是 1/6，那么 dp[i]=(dp[i+1] +dp[i+2]+....dp[i+6])/6 +1 （须要多投掷一次筛子。所以+1）.

②遇到特殊格子时。当前位置的投掷骰子的平均次数等于转移到的位置的平均次数.  比方由x到y。  那么 dp[x]=dp[y]。

依据以上两点。就能够写出代码.

dp[n]是已知的。须要从后往前推。

代码：

#include <iostream>
#include <iomanip>
#include <string.h>
using namespace std;
const int maxn=100005;
double dp[maxn];
int hash[maxn];
int n,m;

int main()
{
    while(cin>>n>>m&&(n||m))
    {
        int x,y;
        memset(hash,0,sizeof(hash));
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            hash[x]=y;//标记一下，x位置的格子是特殊格子
        }
        dp[n]=0;
        for(int i=n-1;i>=0;i--)
        {
            if(hash[i])//特殊格子
                dp[i]=dp[hash[i]];
            else
            {
                double temp=0;
                for(int j=1;j<=6&&i+j<=n;j++)
                    temp+=dp[i+j]/6;
                dp[i]=temp+1;
            }
        }
        cout<<setiosflags(ios::fixed)<<setprecision(4)<<dp[0]<<endl;

    }
    return 0;
}