LightOJ 1030 Solution

Discovering Gold : Solution

#include<bits/stdc++.h>

#define ll long double

#define N 105

using namespace std;

int g[N], n;

ll dp[N];

ll expected_value(int indx)

{

    if(indx == n)

        return g[n];

    if(dp[indx] > 0)

        return dp[indx];

    ll sum = 0;

    int mini = min(6, n-indx);

    for(int i=1;i<=mini;i++)

        sum += (1.0/mini) * expected_value(indx+i);

    dp[indx] = g[indx] + sum;

    return dp[indx];

}

int main()

{

    int t, k = 1;

    cin >> t;

    while(t--)

    {

        cin >> n;

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

        {

            cin >> g[i];

            dp[i] = 0;

        }

        cout << showpoint << fixed << setprecision(7);

        cout << "Case " << k++ << ": " << expected_value(1) << "\n";

    }

    return 0;

}