[dp+期望]Discovering Gold

参考博客：https://www.cnblogs.com/daydayupacm/p/5788115.html

题意

现在有n个格子，每个格子上都有一定的黄金值；还有一个色子（1-6）。起始位置站在格子1上面，若每次投掷色子得到数x,x+i<=n（i表示现处位置的格子编号），则可以到达（x+i）格子上；反之，再进行一次投掷。问：到达标号为n的格子上面，得到黄金的期望值是多少？
期望
一件不确定的事件有确定的所有结果，把第一种的结果值记为s1，它发生的概率记为p1，第二种结果值记为s2，它发生的概率为p2，… 第n种结果值记为sn，它发生的概率记为pn … 那么期望值 Ei= s1p1 + s2p2 +… + sn*pn + …
举例分析：

以第三个例子为例：

3

3 6 9

若我们现处在格子1，那么E1=3+61/2+91/2

（既然我们已经处在格子1了，1格子的黄金我们确定可以拿走了。剩下只有两种情况，要么到达格子2，要么到达格子3，所以两者概率分别为1/2。剩下的情况同理）
关于这道题为什么从后向前求：
已知只能是必定到达最后一个格子。所以要从已知走向位置就是逆着求的

#include <bits/stdc++.h>
#define eps 1e-10
using namespace std;
const int N = 1e3;

double dp[N];
int main()
{
   
	int t,cnt=0,num;
	scanf("%d", &t);
	while(t--) {
   
		int n;
		scanf("%d", &n);
		
		for(int i=1; i<=n; i++) 
		{
   
			scanf("%d", &num);
			dp[i] = num; //init
		}
		for(int i=n-1; i>=1; i--)
		{
   
			int x=min(6, n-i);    //have 6 sides
			for(int j=1; j<=x; j++)
			{
   
				dp[i]+=dp[i+j]*1.0/x;    //从后往前 
			}
		}
		printf("Case %d: %.7lf\n",++cnt, dp[1]+eps);
	}
	return 0;
 }