Mean：
有一个直线的金矿，每个点有一定数量的金子；
你从０开始，每次扔个骰子，扔出几点就走几步，然后把那个点的金子拿走；
如果扔出的骰子超出了金矿，就重新扔，知道你站在最后一个点；
问拿走金子的期望值是多少；
analyse1:
求得每一点的概率即可；
E(X) = X1*p(X1） + X2*p(X2） + …… + Xn*p(Xn) （p为概率，x为某一点价值）。
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include<vector> #include<queue> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1000005; const int INF=0x3f3f3f3f; double p[maxn];///到达每个点的概率 int v[maxn];///每个点的财宝数量 int n; double solve() { if(n==1) return v[1]*1.0; memset(p, 0, sizeof(p)); double sum=0; sum+=(v[1]+v[n]);///点1和点n是肯定能到达 p[1]=1; for(int i=1; i<n; i++) { int d; double k; d=n-i;///当前位置与终点的距离 if(d < 6)///如果小于6，那么从此点到达其他剩余点的概率为1/d;完全因为题目中加了这个条件（如果即将到达的地方超过了这条隧道长度，就重新roll一次） { k=1.0/(1.0*d); for(int j=1; j<=d; j++) p[i+j]=p[i+j]+p[i]*k; } else///如果大于6，那么从此点到达其他剩余点的概率为1/6; { k=1.0/6; for(int j=1; j<=6; j++) p[i+j]=p[i+j]+p[i]*k; } } for(int i=2; i<n; i++)///计算期望值 sum+=v[i]*p[i]; return sum; } int main() { int T, cas=1; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &v[i]); double ans=solve(); printf("Case %d: %.6f ", cas++, ans); } return 0; }
alalyse2:
首先我们假设你现在站在第ｉ个点，且从这个点开始走；
那么这个点的期望p[i] = p[i +1] /6 + p[i + 2] / 6 + p[i + 3] /6 + p[i + 4] / 6 + p[i + 5] / 6 + p[i + 6] / 6 + p[i]；
p[i] 初值就是这个点的金子数量，意思就是这个点的期望，是往后有６种情况，每种的六分之一；
当然情况数少于６的时候要处理一下；
所以从最后一个点往前算一边，就能的的出答案；
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include<vector> #include<queue> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1000005; const int INF=0x3f3f3f3f; double p[maxn];///到达每个点的概率 int v[maxn];///每个点的财宝数量 int n; int main() { int T, cas=1; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &v[i]); p[n]=v[n]; for(int i=n-1; i>=1; i--) { p[i]=v[i]; int dist=6; if(n-i < 6) dist=n-i; for(int j=1; j<=dist; j++) p[i]+=p[i+j]/dist; } printf("Case %d: %.6f ", cas++, p[1]); } return 0; }