题目意思就是,你在下一盘飞行棋,飞行棋大家都下过吧。

现在有n个点从1-N标号,你在0点,给你一个骰子,你抛出得到一个值就可以走到当前坐标+骰子的值的位置。但是有些地方是可以飞过去的。现在给出这些飞过去的坐标,问你走到终点n或者n+投骰子的期望?


我们可以用一个数组保存航班信息,fly[i]=j,代表从i可以飞到j。同样扔出点数为x的概率为p,也就是1/6,递推式是:

dp[i] = dp[fly[i]],      fly[i]!=0;

dp[i] = ∑(dp[i+k]*p) + 1,fly[i]==0;


代码:

StatusAccepted
Time46ms
Memory2912kB
Length698
LangC++
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn=100005;
int n, m, x, y, fly[maxn];
double dp[maxn];
int main()
{
    while(~scanf("%d%d", &n, &m) && n+m){
        memset(fly, 0, sizeof(fly));
        for(int i=0;i<m;i++){
            scanf("%d%d", &x, &y);
            fly[x]=y;
        }
        memset(dp, 0, sizeof(dp));
        for(int i=n-1;i>=0;i--){
            if(fly[i]){
                dp[i]=dp[fly[i]];
            }
            else{
                for(int j=1;j<=6;j++){
                    dp[i]+=dp[i+j]/6.0;
                }
                dp[i]+=1;
            }
        }
        printf("%.4lf\n", dp[0]);
    }
    return 0;
}