本文共 913 字，大约阅读时间需要 3 分钟。

题目大意：通过摇筛子，做0跳到n点，有些点可以直接过渡，问要到达n点，需要摇色子的次数的期望值？

状态转移方程：

首先dp【N】=0；

其次分两种情况：

（1）i点不可以过渡，dp【i】=sum(（dp【i+j】+1）/6)

（2）i点可以过渡到j点，dp【i】=dp[j]

代码如下：

#include
   
    #include
    
     #define MAXN 100005int turn[MAXN];double dp[MAXN];int main(){    int N,M,x,y,i,j;    double temp;    while(scanf("%d%d",&N,&M)&&(N+M))    {        memset(turn,0,sizeof(turn));        while(M--)        {            scanf("%d%d",&x,&y);            turn[x]=y;        }        dp[N]=0;        for(i=N-1;i>=0;i--)        {            if(turn[i])                dp[i]=dp[turn[i]];            else            {                dp[i]=0.0;                for(j=1;j<7;j++)                {                    if(j+i<=N)                        temp=(dp[j+i]+1)/6;                    else                        temp=1.0/6.0;                    dp[i]+=temp;                }            }        }        printf("%0.4lf\n",dp[0]);    }    return 0;}
    
   

转载地址：http://rhuvi.baihongyu.com/