HDU4405 Aeroplane chess (機率DP求期望)

傳送門：HDU 4405 Aeroplane chess

描述：

Aeroplane chess

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3430    Accepted Submission(s): 2180

Problem Description 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.

Please help Hzz calculate the expected dice throwing times to finish the game.

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
        

Source 2012 ACM/ICPC Asia Regional Jinhua Online  

Recommend zhoujiaqi2010   |   We have carefully selected several similar problems for you:   5867  5866  5865  5864  5863 

題意：

跳棋有0~n個格子，每個格子X可以搖一次色子，色子有六面p(1=<p<=6),機率相等，可以走到X+p的位置，有些格子不需要搖色子就可以直接飛過去。問從0出發到達n或超過n搖色子的次數的期望。

思路：

簡單機率dp,去年網絡賽的一道水題，當時水準太差沒過。

dp[i]表示從i出發到達最終位置的次數期望，是以需要逆推。

轉移方程當i需要搖色子時，dp[i]=Σ(1+dp[i+j])/6(1<=j<=6);否則dp[i]=dp[jump[i]] ,其中jump[i]表示從i能夠跳得到的最大位置。

預處理後面的6個位置，直接轉移就行。

全期望公式：http://zh.wikipedia.org/wiki/%E5%85%A8%E6%9C%9F%E6%9C%9B%E5%85%AC%E5%BC%8F

全機率公式：http://zh.wikipedia.org/wiki/%E5%85%A8%E6%A6%82%E7%8E%87%E5%85%AC%E5%BC%8F

機率期望學習：http://kicd.blog.163.com/blog/static/126961911200910168335852/

代碼：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int n,m;
double dp[N];
int jump[N],path[N];

int main(){
  while(~scanf("%d%d",&n,&m)&&(n||m)){
    memset(path, -1, sizeof(path));
    memset(jump, -1, sizeof(jump));//jump[i]表示從i能夠飛的最大的位置
    for(int i=1; i<=m; i++){
      int a,b;scanf("%d%d",&a,&b);
      path[a]=b;//記錄飛一步到達的位置
    }
    for(int i=n; i>=1; i--){
      if(path[i]!=-1){
        int j=path[i];
        if(jump[j]!=-1)jump[i]=jump[j];
        else jump[i]=j;
      }
    }
    for(int i=0; i<6; i++)dp[n+i]=0;
    for(int i=n-1; i>=0; i--){
      if(jump[i]!=-1)dp[i]=dp[jump[i]];
      else{
        double tmp=0;
        for(int j=1; j<=6; j++){
          tmp+=dp[i+j]*(1.0/6.0);
        }
        dp[i]=1+tmp;
      }
    }
    printf("%.4lf\n",dp[0]);
  }
  return 0;
}