借鉴自: https://www.cnblogs.com/keyboarder-zsq/p/6216762.html
题意: n 个格子, 每个格子有一个值. 从 1 开始, 每次扔 6 个面的骰子, 扔出几点就往前几步, 然后把那个格子的金子拿走;
如果扔出的骰子 + 所在位置 > n, 就重新扔, 直到在 n;
问取走这些值的期望值是多少
解析:
- [1] [2] [3] [4] [5] [6] [7] [8] [9]
- // 格子和值都是一样, 所以下述的话, 值就是格子, 格子就是值...
比如这样的 9 个格子, 我们总底往上来
对于第 9 个格子, 因为只有 9, 能取的期望就是 9;
对于第 8 个格子, 8 是一定要取的, 而 9 也是一定回取的, 所以对于第 8 个格子, 期望就是 17;
对于第 7 个格子, 7 是一定要取的, 对于后面可能是直接取了 9, 或者先取 8 再取 9, 情况是满足, 对于每种情况概率是 1/2, 所以就是 7+9/2+(8+9)/2=20;
PS:
上面的情况, 在 7 后面的时候, 我们可能取 9, 或者先取 8, 那么其实就是拿了第 8 个格子的期望和第 9 个格子期望, 期望就是能取的值, 然后 * 概率, 全部情况的总和就是新的期望, 有人会奇怪那 7 呢? 我们的前提是对于第 7 格一定拿 7 啊;
对于第 6 个格子, 那么就是 6 一定要拿的, 然后会拿 7, 拿 8, 拿 9, 他们的期望 * 概率的总和 + 他能取的值就是 6 的第 6 个格子的期望;
... 以此类推;
对于概率的其实一想更简单...
我们一开始就在 1, 概率就是 1, 然后扔一个骰子对于每个面的概率就是 1/6, 那么 dp[i] 代表概率, 每次对能到达的地方更新概率, 最后期望就是值乘以概率的总和 + 1,1 是一定要取的哦~
从后往前推
- import java.math.BigDecimal;
- import java.math.BigInteger;
- import java.text.DecimalFormat;
- import java.util.ArrayList;
- import java.util.Collection;
- import java.util.Collections;
- import java.util.Comparator;
- import java.util.LinkedList;
- import java.util.Queue;
- import java.util.Scanner;
- import java.util.Stack;
- import java.util.Vector;
- public class Main {
- public static void main(String[] args) {
- final int maxn = 10010;
- Scanner cin = new Scanner(System.in);
- int T = cin.nextInt();
- int cnt = 0;
- while(T-- != 0)
- {
- double[] dp = new double[maxn];
- int n = cin.nextInt();
- for(int i=1;i<=n;i++)
- dp[i] = cin.nextDouble();
- for(int i=n-1;i>=1;i--)
- {
- int k = Math.min(6, n-i);
- for(int j=i+1;j<=i+k;j++)
- {
- dp[i] += dp[j]/(double)k;
- }
- }
- System.out.printf("Case %d: %.10f\n",++cnt,dp[1]);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2605302.html