「NOI2005」聪聪和可可 的 题解

「NOI2005」聪聪和可可 的 题解

读题

在图上做概率DP

前置

先用 BFS 预处理出两点间的距离 \(dis_{i,j}\)

在预处理出 \(i\) 要到 \(j\) 下一步要往哪里走 \(nxt_{i,j}\)

显然，\(nxt_{i,j}\) 可以通过遍历 \(i\) 的每一个子节点 \(k\)

检查是否在最短路径 即 \(1 + dis_{k, j} = dis_{i,j}\) 上来实现

• 注意这里要对子节点排序，因为题目上说 \(如果这样的景点有多个，她会选一个标号最小的景点。\)

DP

因为是在图上，考虑用记忆化搜索来实现

• 状态定义

  \(f_{i,j}\) 表示猫在 \(i\) ， 老鼠在 \(j\) 时猫想抓到老鼠的期望距离

• 状态转移

  1. \(i = j\) 直接吃掉 \(f_{i,j} = 0\)

  2. \(dis_{i,j} <= 2\) 走一个时间单位 吃掉 \(f_{i,j} = 1\)

  3. 枚举老鼠的下一个节点 \(k\)

     \(f_{i,j} = f_{nxt_{i,k}, k} / (p + 1) + f_{nxt_{i,j}, j} / (p + 1) + 1\)

     还有留着原地的情况