首页 > 代码库 > LightOJ 1030 Discovering Gold （期望）
LightOJ 1030 Discovering Gold （期望）
https://vjudge.net/problem/LightOJ-1030
题意：
在一个1×N的格子里，每个格子都有相应的金币数，走到相应格子的话，就会得到该格子的金币。
现在从1格子开始，每次摇骰子，他就前进几步，但有一种情况例外，如果当前位置＋色子数 > N,那么他就会重新摇色子。
走到N这个位置的话，意味着游戏结束了。
问游戏结束时，这个人得到金币的期望。
思路：
这里给出两种做法，一种是正序求解，一种是逆序求解。
①正序求解：
这种做法是从前往后计算每个格子的概率，假设我们现在处于第i个格子，它后面还有k=min（n-i，6）个格子，那么通过这个格子，我们就可以到达它后面的格子，现在它后面第j（1<=j<=k）个格子的概率就要加上d[i] / k。仔细想一想的话，其实就是个全概率。自己不太能讲得清，具体还是看代码吧。
②逆序求解：
这种做法是从后往前计算，也就是概率dp。d[i]表示以i为起点的格子所能获得的期望。
当我们要计算d[i]的时候，d[i]+=1/k*d[i+j]。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,int> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn = 100 + 5;17 18 int n;19 20 int a[maxn];21 double r[maxn];22 23 int main()24 {25 //freopen("in.txt","r",stdin);26 int T;27 int kase=0;28 scanf("%d",&T);29 while(T--)30 {31 scanf("%d",&n);32 for(int i=1;i<=n;i++) scanf("%d",&a[i]);33 34 memset(r,0,sizeof(r));35 36 r[1]=1;37 for(int i=1;i<=n;i++)38 {39 int k=6;40 while(i+k>n) k--;41 for(int j=1;j<=k;j++)42 {43 r[i+j]+=r[i]*(1.0/k);44 }45 }46 47 double ans=0;48 for(int i=1;i<=n;i++)49 ans+=r[i]*a[i];50 51 printf("Case %d: ",++kase);52 printf("%.7f\n",ans);53 }54 return 0;55 }
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,int> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn = 100 + 5;17 18 int n;19 20 double a[maxn];21 22 int main()23 {24 //freopen("in.txt","r",stdin);25 int T;26 int kase=0;27 scanf("%d",&T);28 while(T--)29 {30 scanf("%d",&n);31 for(int i=1;i<=n;i++) scanf("%lf",&a[i]);32 33 34 for(int i=n-1;i>=1;i--)35 {36 int k=min(6,n-i);37 for(int j=1;j<=k;j++)38 {39 a[i]+=1./k*a[i+j];40 }41 }42 43 printf("Case %d: ",++kase);44 printf("%.7f\n",a[1]);45 }46 return 0;47 }
LightOJ 1030 Discovering Gold （期望）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。