「HLOI2016」小明的智力游戏

Posted on In
HLOI2016 Day1 T2

题目描述

小明喜欢玩一些智力游戏。假设有一个一维棋盘，在该棋盘上从左至右共有 个格子，编号从 到 。小明有一个棋子，最初在编号为 的格子中。他每次掷两个骰子，每个骰子都有六个面，而且掷到每个面的概率都相同，骰子的点数分别是 。当棋子在编号为 的格子中时，掷到的两个骰子点数分别是 和 ，那么棋子将会移动到编号为 的格子中。当 大于或等于 的时候，小明就结束游戏。

小明是一个比较喜欢偷懒的人，他不喜欢掷那么多次骰子，所以在棋盘中有 条飞行线路，对于第 条飞行线路来说，可以不用掷骰子直接从编号为 的格子跳到编号为 的格子。如果还有另一条飞行线路起点是编号 的格子，那么小明就可以按照这条线路继续向前跳动。保证每个格子只可以作为一条飞行路线的起点。

现在想知道完成这个游戏需要掷骰子的次数期望值是多少。

输入

第一行给出 ，；

接下来 行，每行包括两个整数 ，表示格子 到格子 有一条飞行线路。

输出

输出包含一个整数，即相应输入的答案。输出完成这个游戏需要掷骰子的次数期望值是多少，结果保留小数点后 位。

样例 1

样例输入

1
2 0

样例输出

1
1.0000

样例 2

样例输入

1
2
3
4
8 3
2 4
4 5
7 8

样例输出

1
1.4213

数据范围及约定

对于 的数据，保证 ；

对于 的数据，保证 ；

对于 的数据，保证 。

时间限制与空间限制

时间限制：，空间限制：。

题解

半黑历史题……期望 DP。

如果直接从前向后推的话，因为飞行路线的存在推不了。所以倒着推，就可以避免这个问题。

所以，DP 转移方程为：

还有，题目中貌似没说，每个格子的出度为 ……

如果有飞行路线，直接继承终点的期望值即可。

时间复杂度 ，空间复杂度 。

代码见这里。