簡單概率dp(期望)-hdu-4405-Aeroplane chess

題目大意：   跳棋有0~n個格子，每個格子X可以搖一次色子，色子有六面p(1=<p<=6),概率相等，可以走到X+p的位置，有些格子不需要搖色子就可以直接飛過去。問從0出發到達n或超過n搖色子的次數的期望。   解題思路：   簡單概率dp,去年網絡賽的一道水題，當時水平太差沒過。   dp[i]表示從i出發到達最終位置的次數期望。   轉移方程當i需要搖色子時，dp[i]=Σ(1+dp[i+j])(1<=j<=6);否則dp[i]=dp[jump[i]] 表示從i能夠跳得到的最大位置。   預處理後面的6個位置，直接轉移就行。   代碼：

 
#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#include<ctime>  
#define eps 1e-6  
#define INF 0x3fffffff  
#define PI acos(-1.0)  
#define ll __int64  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 110000  
#define Maxm 1100  
  
double dp[Maxn];  
int path[Maxn],jump[Maxn],n,m;  
  
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 tt=0;  
               for(int j=1;j<=6;j++)  
               {  
                   tt+=dp[i+j]*(1.0/6.0);  
               }  
               dp[i]=1+tt;  
           }  
       }  
       printf("%.4f\n",dp[0]);  
  
   }  
   return 0;  
}