Light OJ 1030 - Discovering Gold

题目大意：

给你一个1*N的方格，你初始位置是在1，给你一个骰子，假设你现在的位置是X，你投掷一个骰子掷的点数是y，那么你的新位置就是 X+y, 并且你可以得到新位置的宝藏。假如X+y > N了

那么就需要重新投掷，知道满足条件为止。输出你得到黄金的预计期望。

=========================================================================================

概率DP，用记忆化搜索比较好。

DP[i], 代表从i点到达，第n个点所能达到的最大值。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

const int INF = 1e9+;

const int MAXN = ;

int n;

double dp[MAXN], a[MAXN];

///dp[从i到达终点] = 期望

double DFS(int cur)

{

    if(dp[cur] != -)

        return dp[cur];

    int cnt = min(n-cur, );///代表当前格子可以向向前移动多少个位置

    dp[cur] = ;

    for(int i=cur+; i<=cur+cnt; i++)

        dp[cur] += 1.0/cnt * DFS(i);

    dp[cur] += a[cur];

    return dp[cur];

}

int main()

{

    int T, cas = ;

    scanf("%d", &T);

    while(T --)

    {

        scanf("%d", &n);

        for(int i=; i<=n; i++)

        {

            scanf("%lf", &a[i]);

            dp[i] = -;

        }

        dp[n] = a[n];

        printf("Case %d: %.6lf\n", cas++, DFS());

    }

    return ;

}

/*

3

3

1 2 3

*/

秒客网

Light OJ 1030 - Discovering Gold

相关文章