# 简单概率DP——hdu4405

Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the numbers on the faces are
1,2,3,4,5,6). When Hzz is 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.

Input

There are multiple test cases.

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.

Output

For each test case in the input, you should output a line indicating the expected dice throwing times. Output should be rounded to 4 digits after decimal point.

Sample Input

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

Sample Output

```1.1667
2.3441

```

```/*******************************************************************************/
/* OS           : Linux fc20.x86_64 #1 SMP Tue Dec  UTC 2013 x86_64  GNU/Linux
* Compiler     : 4.8.2 20131212 (Red Hat 4.8.2-7) (GCC)
* Encoding     : UTF8
* Date         : 2014-04-02
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 100005
int x[N],y[N],mp[N];
double dp[N];
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int n,m;
while(cin>>n>>m&&(n||m))
{
int i=0;
memset(mp,-1,sizeof(mp));
memset(dp,0,sizeof(dp));
while(i++<m)
{
cin>>x[i]>>y[i];
mp[x[i]]=y[i];
}
for(i=n-1;i>=0;i--)
{
if(mp[i]!=-1)dp[i]=dp[mp[i]];
else
{
for(int j=1;j<=6;j++)
dp[i]+=dp[i+j];
dp[i]=dp[i]/6+1;
}
}
printf("%.4f\n",dp[0]);

}
return 0;
}
```

## POJ 3071 Football（简单 概率DP）

Football 原文链接:http://blog.csdn.net/xuechelingxiao/article/details/38520105 大意:2^n 个球队进行单场淘汰赛,每两只球队之间比赛会有胜负的概率,问最后谁夺冠的概率最大. 思路:简单的概率DP问题,主要是怎么处理哪两个球队比赛的问题. DP方程为 dp[i][j] = ∑(dp[i-1][j]*dp[i-1][k]*p[j][k]); //dp[i][j]表示第 i 轮的时候,第 j 支队伍赢的概率.. 对于其中位运算,可

## Aeroplane chess(简单概率dp)

Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the numbers on the faces are 1,2,3,4,5,6). Whe

## Josephina and RPG 简单概率DP

Josephina and RPG 题目抽象:给出R=C(m,3)个队伍之间的胜率.给出需要挑战的n个队伍(按顺序).玩家最开始从R个队伍中任选一支队伍去挑战,当挑战某队伍成功时,可以将当前的队伍与挑战成功的队伍交换,也可以继续选择该队伍.  求最大的胜率. 思路:物理递推法. /*                    dp[i+1][j]            dp[i][j]=                    dp[i+1][num[i]]*/ 1 #include <iostrea

## CodeForces 540D Bad Luck Island 概率dp

CodeForces 540D 应该是简单概率dp,由于写得少显得十分蠢萌 求期望逆推,求概率正推,大概是这么个意思,贴一发留恋 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define db double const int maxn=108; db dp[maxn][maxn][maxn]; int main() { int i,j,n,m,k,p; whi

## Throwing Dice(概率dp)

C - Throwing Dice Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%lld & %llu LightOJ 1064 uDebug Description n common cubic dice are thrown. What is the probability that the sum of all thrown dice is at least x? Input Input starts wit

## hdu 3853 概率DP 简单

http://acm.hdu.edu.cn/showproblem.php?pid=3853 题意:有R*C个格子,一个家伙要从(0,0)走到(R-1,C-1) 每次只有三次方向,分别是不动,向下,向右,告诉你这三个方向的概率,以及每走一步需要耗费两个能量,问你走到终点所需要耗费能量的数学期望: 回头再推次,思想跟以前的做过的类似 注意点:分母为0的处理 #include <cstdio> #include <cstring> #include <algorithm>

## hdu4405概率dp入门

Aeroplane chess Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1122    Accepted Submission(s): 762 Problem Description Hzz loves aeroplane chess very much. The chess map contains N+1 grids lab