题目描述
从左到右有n个方格，每一块方格上有x[i] 块黄金，最初站在第一块方格上，有一个6个面的均匀骰子，
每一个面上的 权值 是1−6，每次掷骰子之后按照点数y跳到y步之后的方格，如果超出范围，则重新掷骰子，问到达第n个方格能得到的期望黄金数。
输入
第一行两个整数n(1<=n<=1000)。
第二行n个整数,第i个整数为x[i],(1<=x[i]<=1000)。
输出
输出一个实数表示答案，结果误差范围取10-6。
样例输入
3 3 6 9
样例输出
15
提示
样例解释
对于这个样例，第一次仅掷1或2满足题意，可以认为两种情况概率均为50%。
掷1：从黄金数3的格子走到黄金数6的格子，之后只能选择黄金数9的格子，获得黄金数3+6+9=18；
掷2：从黄金数3的格子直接到黄金数9的格子，获得黄金数3+9=12；
因此获得黄金数期望=1250%+1850%=15
对于10%的数据，1<=n<=10
对于50%的数据，1<=n<=100
对于100%的数据，1<=n<=1000
附上本题引路人：https://blog.csdn.net/weixin_45675097
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} ///#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) ///char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; #define start int wuyt() #define end return 0 int cnt; string s; int num[maxn]; double num2[maxn]; start { int n=read;num2[1]=1.0; double ans=0; for(int i=1;i<=n;i++) num[i]=read; for(int i=1;i<=n;i++) { int temp=min(n-i,6); for(int j=1;j<=temp;j++) num2[i+j]+=num2[i]*(1.0/temp); } for(int i=1;i<=n;i++) ans+=num2[i]*num[i]; printf("%.10f",ans); end; } /************************************************************** Language: C++ Result: 正确 Time:1 ms Memory:4368 kb ****************************************************************/
