[水+期望dp] light oj 1030 Discovering Gold

题意：

给n个点，，每个点都有一个财宝。

你从1这个点开始出发，假设你在i这个点，每次随机走1~min(6,n-i)步。

每到达一个点就拿走财宝。

问最后拿到财宝的期望。

思路：

水的题目。

dp[n]=v[n]

然后逐个往前推。

就是注意一下步数是 1~min(6,n-i)

代码：

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"#include"map"#include"stack"#include"vector"#define ll __int64#define inf -999999999999999999LLusing namespace std;int main(){int t,cas=1;cin>>t;while(t–){int n;scanf("%d",&n);int v[123];double dp[123];for(int i=1;i<=n;i++) scanf("%d",&v[i]);memset(dp,0,sizeof(dp));dp[n]=v[n];for(int i=n-1;i>=1;i–){int cnt=min(6,n-i);dp[i]=v[i];for(int j=1;j<=cnt;j++){dp[i]+=1.0/cnt*dp[i+j];}}printf("Case %d: %.7f\n",cas++,dp[1]);}return 0;}

人生谁无少年时，甜苦酸辛各自知。