LightOJ

题目链接：https://vjudge.net/problem/LightOJ-1030

1030 - Discovering Gold

PDF (English)

Statistics

Forum

Time Limit: 2 second(s)

Memory Limit: 32 MB

You are in a cave, a long cave! The cave can be represented by a 1 x N grid. Each cell of the cave can contain any amount of gold.

Initially you are in position 1. Now each turn you throw a perfect 6 sided dice. If you get X in the dice after throwing, you add X to your position and collect all the gold from the new position. If your new position is outside the cave, then you keep throwing again until you get a suitable result. When you reach the N^th position you stop your journey. Now you are given the information about the cave, you have to find out the expected number of gold you can collect using the given procedure.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a blank line and an integer N (1 ≤ N ≤ 100) denoting the dimension of the cave. The next line contains N space separated integers. The i^th integer of this line denotes the amount of gold you will get if you come to the i^th cell. You may safely assume that all the given integers will be non-negative and no integer will be greater than 1000.

Output

For each case, print the case number and the expected number of gold you will collect. Errors less than 10^-6 will be ignored.

Sample Input	Output for Sample Input
3 1 101 2 10 3 3 3 6 9	Case 1: 101.0000000000 Case 2: 13.000 Case 3: 15

题意：

在水平线上有n个格，每个格有价值若干的黄金。人从第一个位置开始，每次先摇骰子，然后再跳到新的格子，如果新格子在n格之外，则重新摇骰子，直到到达n。问得到的黄金的平均值。

题解：

1.可知从i跳到i+1~i+6的概率是相等的，所以：dp[i] = (dp[i+1]+……+dp[i+6])/6 + val[i]。

2.根据上述式子，可知要从后面往前递推。当然不足6的需要特殊处理。

易错点：

开始做的时候，想到的是从前往后递推：dp[i] = (dp[i-1]+……+dp[i-6])/6 + val[i] 。

然而从i-6~i-1到i的概率不一定是相等的，因为他们不在同一次抛筛子。

但是从后往前递推的话，从i跳到i+1~i+6的概率是相等的，因为都是在i的位置抛骰子决定的。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 1e2+100;

double val[MAXN], dp[MAXN];
int main()
{
    int T, n, kase = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 1; i<=n; i++)
            scanf("%lf", &val[i]);

        dp[n] = val[n];
        for(int i = n-1; i>=1; i--)
        {
            int Last = min(i+6,n), cnt = Last - i;
            dp[i] = val[i];
            for(int j = i+1; j<=Last; j++)
                dp[i] += dp[j]/cnt;
        }
        printf("Case %d: %.10lf
", ++kase, dp[1]);
    }
}