LightOj_1030 Discovering Gold
LightOj_1030 Discovering Gold
若羽
发布于 2019-07-15 16:09:57
发布于 2019-07-15 16:09:57
题意：
在一个1 X N 的格子上， 每个格子都有一定的黄金， 你从第一个格子出发， 问到最后一个格子得到黄金的期望。
每次前进使用骰子投点来决定前进步数， 如果投出的点前进后会超过N， 那么就重新投掷。
思路：
很直接的期望题。
概率dp求期望是从后往前求， 每次的概率为 1 / 6.
dp[i] = 1/6 * (dp[i + 1] + dp[i + 2] + dp[i + 3] + dp[i + 4] + dp[i + 5] + dp[i + 6]) + x[i].
根据投掷的点数加上当前的位置会不会超过N来确定括号里面加的项， 还有概率。
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define MAXN 110
19 #define MOD 1000000007
20 #define eps 1e-6
21 int n;
22 double dp[MAXN];
23
24 int main()
25 {
26 int T;
27 int kcase = 0;
28 scanf("%d", &T);
29 while(T --)
30 {
31 scanf("%d", &n);
32 for(int i = 1; i <= n; i ++)
33 scanf("%lf", &dp[i]);
34 for(int i = n - 1; i >= 1; i --)
35 {
36 if((n - i) >= 6)
37 for(int j = 1; j <= 6; j ++)
38 dp[i] += dp[i + j] / 6.0;
39 else
40 for(int j = 1; j <= (n - i); j ++)
41 dp[i] += dp[i + j] / (double)(n - i);
42 }
43 printf("Case %d: %.7lf\n", ++ kcase, dp[1]);
44 }
45 return 0;
46 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-08-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读