ACM模版

描述

题解

概率 DP ，求期望。

状态转移方程很容易想，设 dp[i] 表示在位置 i 还需要多少期望才能到达终点，那么 dp[n]=0 ，求 dp[0] 即可。

状态转移方程如下：

dp[i]=∑x=16dp[i+x]6.0+1

但是题目中提到了传送门，也就是说当到达 a 时直接飞到 b (a<b) ，那么这种情况要对 dp[] 进行特判，使 dp[a]=dp[b] 。

剩下的就没有什么问题了，具体看代码吧！

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

#define ll long long

const int MAXN = 1e5 + 10;

int n, m;
int vis[MAXN];
double dp[MAXN];

int main()
{
    while (~scanf("%d%d", &n, &m) && n + m)
    {
        memset(dp, 0, sizeof(dp));
        memset(vis, -1, sizeof(vis));

        int a, b;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &a, &b);
            vis[a] = b;
        }

        for (int i = n - 1; i >= 0; i--)
        {
            if (vis[i] == -1)
            {
                for (int j = 1; j <= 6; j++)
                {
                    dp[i] += dp[i + j] / 6.0;
                }
                dp[i] += 1;
            }
            else
            {
                dp[i] = dp[vis[i]];
            }
        }

        printf("%.4lf\n", dp[0]);
    }

    return 0;
}