hdu 4405 Aeroplane chess(概率DP)

题目链接：hdu 4405 Aeroplane chess

题意：

一个0到n的数轴上掷色子前进，中间有直达部分，问到终点需要掷色子的期望。

题解：

无环的期望DP，直接递推就行。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

const int N=1e5+7;
double dp[N];
int n,m,vis[N];

int main(){
    while(scanf("%d%d",&n,&m),n+m)
    {
        F(i,0,n)vis[i]=-1;
        F(i,1,m)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            vis[x]=y;
        }
        F(i,0,n+6)dp[i]=0;
        for(int i=n-1;i>=0;i--)
        {
            if(vis[i]!=-1){dp[i]=dp[vis[i]];continue;}
            F(j,1,6)dp[i]+=dp[i+j]/6;
            dp[i]+=1;
        }
        printf("%.4f
",dp[0]);
    }
    return 0;
}