简单概率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;  
}

补充：移动开发 , Android ,