题目链接:https://vjudge.net/contest/299639#problem/B
题目大意:
n个格子,每个格子有一个值。从1开始,每次扔6个面的骰子,扔出几点就往前几步,然后把那个格子的金子拿走;如果扔出的骰子+所在位置>n,就重新扔,直到在n;问取走这些值的期望值是多少;

这种结局一定的事件:概率只能正推,期望只能逆推。

一个格子可以由前面6个格子转移而来。

概率dp:

//dp[i]途中经过i格子的概率
//期望值=∑(dp[i]*a[i])

#include<bits/stdc++.h>
#define LL long long
using namespace std;

double dp[103];
double a[105];
int main()
{
    int t, CUT=0;
    scanf("%d",&t);
    while(t--)
    {
        CUT++;
        int n;
        double ans=0;
        memset(dp, 0, sizeof(dp));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lf",&a[i]);
        }
        dp[1]=1;
        for(int i=1;i<=n;i++)
        {
            int cut=min(n-i, 6);
            for(int j=1;j<=cut;j++)
            {
                dp[i+j]+=dp[i]*(1.0/cut);
            }
            ans+=dp[i]*a[i];
        }

        printf("Case %d: %.7f\n",CUT, ans);
    }

    return 0;
}

期望dp:

//dp[k]为到达k这个位置时得到金币的期望
//因为结果一定所以从n推到1
//期望值=dp[1]
#include<bits/stdc++.h>
#define LL long long
using namespace std;

double dp[105];
int main()
{
    int t, CUT=0;
    scanf("%d",&t);
    while(t--)
    {
        CUT++;
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lf",&dp[i]);
        }
        int cut=1;
        for(int i=n-1;i>=1;i--)
        {
            cut=min(6, cut);
            for(int j=1;j<=cut;j++)
            {
                dp[i]+=dp[i+j]*(1.0)/cut;
            }
            cut++;
        }
        printf("Case %d: %.7f\n",CUT, dp[1]);
    }

    return 0;
}