hdu 4405 Aeroplane chess（機率dp）

題目連結：

http://acm.hdu.edu.cn/showproblem.php?pid=4405

解題思路：

題目大意： 并排的0~n的格子，起始點在0，每次向前走時都要擲骰子1~6,得到x，之後往前走x步，還有一些特殊的連接配接xi,yi, 如果到達xi就直接跳到yi不用擲骰子，求到達>=n擲骰子的次數的期望。

算法思想：

求機率正推，求期望反推。

式子很明顯,E(w) 表示目前在w這個格子要達到條件(>=n)擲骰子次數的期望

如果存在(xi, yi),使得 w == xi, 則E(w) = E(yi) , 否則E(w) = ∑(E(w+i)/6) + 1 ，i從1到6

之後從後往前遞推即可，答案就是E(0).

AC代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

map<int,int> mm;
double dp[100005];

int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m),n+m){
        mm.clear();
        int x,y;
        for(int i = 0; i < m; i++){
            scanf("%d%d",&x,&y);
            mm[x] = y;
        }
        memset(dp,0,sizeof(dp));
        for(int i = n-1; i >= 0; i--){
            if(mm[i])
                dp[i] = dp[mm[i]];//走捷徑
            else{
                for(int j = 1; j <= 6; j++)
                    dp[i] += 1.0/6*(dp[i+j]+1);//到達i的狀态是由(i+1....i+6)來的
            }
        }
        printf("%.4lf\n",dp[0]);
    }
    return 0;
}