Aeroplane chess
at grid i and the dice number is x, he will moves to grid i+x. Hzz finishes the game when i+x is equal to or greater than N.
There are also M flight lines on the chess map. The i-th flight line can help Hzz fly from grid Xi to Yi (0<Xi<Yi<=N) without throwing the dice. If there is another flight line from Yi, Hzz can take the flight line continuously. It is granted that there is
no two or more flight lines start from the same grid.
Please help Hzz calculate the expected dice throwing times to finish the game.
Each test case contains several lines.
The first line contains two integers N(1≤N≤100000) and M(0≤M≤1000).
Then M lines follow, each line contains two integers Xi,Yi(1≤Xi<Yi≤N).
The input end with N=0, M=0.
2 0 8 3 2 4 4 5 7 8 0 0
1.1667 2.3441
题意：有1个1*(n+1)的格，下标为0~n ;起始于0格，每步掷一次骰子，掷到i，前进i步，某些格子可以直达别的格子无需掷骰子，问到达>=n位置所需掷骰子次数的期望。
思路：总期望为子期望的加权和，加权因子为状态转移概率。设dp[ i ]为从i开始到达目标状态的期望,dp[ i ]有6种转移方式：
（1）dp[ i ] ------>dp[ i + 1 ] , 转移概率为1/6;
（2）dp[ i ] ------>dp[ i + 2 ] , 转移概率为1/6;
（3）dp[ i ] ------>dp[ i + 3 ] , 转移概率为1/6;
（4）dp[ i ] ------>dp[ i + 4 ] , 转移概率为1/6;
（5）dp[ i ] ------>dp[ i + 5 ] , 转移概率为1/6;
（6）dp[ i ] ------>dp[ i + 6 ] , 转移概率为1/6;
所以dp[ i ] =1 / 6 * ( ( dp[ i + 1 ] + 1 ) + ( dp[ i + 2 ] + 1 ) + ( dp[ i + 3 ] + 1 ) + ( dp[ i + 4 ] + 1 ) + ( dp[ i + 5 ] + 1 ) + ( dp[ i + 6 ] + 1 ) ) ,
化简得：dp[ i ] =1 + 1 / 6 * ( ( dp[ i + 1 ] ) + ( dp[ i + 2 ] ) + ( dp[ i + 3 ] ) + ( dp[ i + 4 ] ) + ( dp[ i + 5 ] ) + ( dp[ i + 6 ] ) );
不过注意：转移的前提是没有直达的情况，所以之间需要判是否存在直达，若存在直接赋值。详见代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100000+100;
int n,m;
double dp[MAXN];
int vis[MAXN];
int main()
{
// freopen("text.txt","r",stdin);
while(~scanf("%d%d",&n,&m) && n+m)
{
memset(vis,0,sizeof(vis));
for(int i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
vis[x]=y;
}
memset(dp,0,sizeof(dp));
for(int i=n-1;i>=0;i--)
{
if(vis[i])
{
dp[i]=dp[vis[i]];
continue;
}
dp[i]=1.0+1.0/6.0*(dp[i+1]+dp[i+2]+dp[i+3]+dp[i+4]+dp[i+5]+dp[i+6]);
}
printf("%.4f\n",dp[0]);
}
return 0;
}