[省选] [DP] HLOI2016Day1 小明的智力游戏

问题描述 Description

小明喜欢玩一些智力游戏。假设有一个一维棋盘，在该棋盘上从左至右共有N+1$N+1$个格子，编号从0$0$到N$N$。小明有一个棋子，最初在编号为0$0$的格子中。他每次掷两个骰子，每个骰子都有六个面，而且掷到每个面的概率都相同，骰子的点数分别是1,2,3,4,5,6$1,2,3,4,5,6$。 当棋子在编号为a$a$的格子中时，掷到的两个骰子点数分别是x$x$和y$y$，那么棋子将会移动到编号为a+x+y$a+x+y$ 的格子中。当a+x+y$a+x+y$大于或等于N$N$的时候，小明就结束游戏。 小明是一个比较喜欢偷懒的人，他不喜欢掷那么多次骰子，所以在棋盘中有M$M$条飞行线路，对于第i$i$条飞行线路来说，可以不用掷骰子直接从编号为u$u$的格子跳到编号为v$v$的格子。如果还有另一条飞行线路起点是编号v(0<u<v≤n)$v(0/lt u/lt v/le n)$ 的格子，那么小明就可以按照这条线路继续向前跳动。保证每个格子只可以作为一条飞行路线的起点。 现在想知道完成这个游戏需要掷骰子的次数期望值是多少。

输入 Input

第一行给出N$N$，M$M$。 接下来M$M$行，每行包括两个整数u,v(0<u<v≤n)$u,v (0/lt u/lt v/le n)$，表示格子u$u$到格子v$v$有一条飞行线路。

输出 Output

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

样例输入#1 Sample Input #1

2 0

样例输出#1 Sample Output #1

1.0000

样例输入#2 Sample Input#2

8 3 2 4 4 5 7 8

样例输出#2 Sample Output#2

1.4213

限制 Limits

对于30%的数据，保证1≤=N≤100,0≤M≤10$1/le=N/le 100,0/le M/le 10$。 对于60%的数据，保证1≤N≤1000,0≤M≤100$1/le N/le 1000,0/le M/le 100$。 对于100%的数据，保证1≤N≤105,0≤M≤1000$1/le N/le 10^5,0/le M/le 1000$。 Time Limit : 1s$1s$ & Memory Limit : 128MB$128MB$

半黑历史题……期望DP（话说学校还没讲期望23333333） 如果直接从前向后推的话，因为飞行路线的存在推不了。所以倒着推，就可以避免这个问题。 所以，DP方程式为 dp[i]+=∑j=212(dp[i+j]+1)∗p[j] $$/begin{equation}dp[i]+=/sum_{j=2}^{12}(dp[i+j]+1)*p[j]/end{equation}$$ 还有，题目中貌似没说，每个格子的出度为1…… 如果有飞行路线，直接继承终点的dp值即可。 时间复杂度O(n)$O(n)$ Code