yhz012 发布于四月 13, 2020 分享 发布于四月 13, 2020 (已修改) 艹这就突然变成我老本行了（x 我拿particle filter做可以不，暴力模拟的（ 等我刷完牙开始写好了，已经有想法了 为了方便我就把格子从0开始编号了，所以会和题目中的编号差1，不过不影响大局。 首先需要一个概率论非常重要的性质，即期望的线性性 —— 定理1 可以表述为E( sum_i (k_i X_i) ) = sum_i ( k_i E(X_i))，其中的k为常数X为随机变量 我们考虑最简单的情况，终点在1 有期望 = 1 * 1 = 1，即1的概率走至少1格，花费1步 终点在2时，我们有 1/6的概率走到1，花费1步，然后变成剩下1格的情况，即期望1。以及5/6的情况花费一步直接到位。即期望 1/6 * (1 + 1) + 5/6 = 7/6 终点在3时，我们有 1/6走到1，花费1，变成剩下2格。1/6走到2，花费1，变成剩下1格，4/6的情况一步到位。即期望1/6 * (1 + 7/6) + 1/6 * (1 + 1) + 4/6 * 1 = 49/36 终点4同理，有 1/6 * (1 + 49/36) + 1/6 * (1 + 7/6) + 1/6 * (1 + 1) + 3/6 * 1 = 343/216 终点5同理，有 1/6 * (1 + 343/216) + ... = 2401/1296 终点6同理有 16807/7776 ok，现在初始表格填完了，接下来考虑递推，因为显然终点在至少是7的时候不存在1步到位的情况了，所以是通项公式 终点在k的时候我们有花1步把问题变为 1/6概率终点在k-1 1/6概率终点在k-2 1/6概率终点在k-3 1/6概率终点在k-4 1/6概率终点在k-5 1/6概率终点在k-6 利用定理1，得到K = 1 + 1/6 (K-1 + K-2 + K-3 + K-4 + K-5 + K-6)，其中大写K为终点在K时的期望步数，K-x同理。 至此，如果无传送门，得解。（注：这里可以用类似斐波那契数列的矩阵求法类似的方式直接得到通项公式） —— 公式1 为了解决传送门问题，首先我们需要准确知道到各传送门的概率。 类似的方法，初始化-5~-1号格子为0， 0号格子为1，对格子k有 K = 1/6 (K-1 + K-2 + K-3 + K-4 + K-5 + K-6)，其中大写K为走到格子K的概率，K-x同理。 —— 公式2 需要注意的是，对于传送门实际上我需要精确的刚好走到这一格的期望，因为错过了就凉了，所以需要求的期望和上面的终点期望稍微有一些不同 举例来说1是(1 * 1/6) / 1/6 = 1，2是(2 * 1/36 + 1 * 1/6) / (1/36 + 1/6)，3是(3 * 1/6^3 + 2 * 1/6^2 * 2 + 1 * 1/6) / (1/6^3 + 1/6^2 * 2 + 1/6)…… 不过同样的对于7及以上可以得到和公式1一样的递推公式 —— 公式3 实际上这里我们已经得到了精确地走到每个格子的期望，为了转化成最终结果，只需要对最后6个格子的递推公式改一下，把置零的部分变成置一就可以了 然后传送门可以理解为将a端的期望直接复制给b端即可（ab可互换）（当然是选择留小的就是了这句有很大问题 想了下基本上已经可以做了 公式3依然可以暴力做成矩阵的通项公式的形式，然后对于传送门两侧update一下之后继续用递推公式暴力打表就好了，最后用最后6个格子的期望稍微处理一下就完了 四月 13, 2020，由yhz012修改 注释 Mr.K 018 50.00节操 辛苦了~ 链接到点评
yhz012 发布于四月 13, 2020 分享 发布于四月 13, 2020 22 分钟前, Muriya Tensei 说道: 那么对于飞行通道描述中的，可以选择飞也可以不飞，如何理解 首要的目的是快速通关还是 完全随机（那不就是1/2飞了么），如果为了快速通关，也不必要双向啊 有必要的，举例来说我现在一共100格子，有通道1-51，48-52，49-100 链接到点评
yhz012 发布于四月 13, 2020 分享 发布于四月 13, 2020 1 分钟前, Muriya Tensei 说道: 默认会选择最优的走法吗（比如你举的这个例子，如果51到了52，是否飞回48,），计算期望选择还是emmm 这部分以我的理解是玩家自己选择的，所以肯定对于玩家来说是主动选择最优解法 链接到点评
推荐贴