AC. 梦想

frank_c1

[BZOJ 1415] 聪聪和可可

发布于2016年04月10日 | 暂无评论 | 1,154阅读 | 动态规划,概率论

题目描述

2016041001

输入格式

数据的第1行为两个整数N和E,以空格分隔,分别表示森林中的景点数和连接相邻景点的路的条数。 第2行包含两个整数C和M,以空格分隔,分别表示初始时聪聪和可可所在的景点的编号。 接下来E行,每行两个整数,第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。 所有的路都是无向的,即:如果能从A走到B,就可以从B走到A。 输入保证任何两个景点之间不会有多于一条路直接相连,且聪聪和可可之间必有路直接或间接的相连。1≤N,E≤1000

输出格式

输出1个实数,四舍五入保留三位小数,表示平均多少个时间单位后聪聪会把可可吃掉。

题目解析

这题的概率转移网络非常明显。令trans(x,c)为聪聪在x,可可在c时聪聪会去往的点。令dp(i,j)为聪聪在i,可可在j到终止状态的期望时间。在i = j时,dp(i,j) = 0。若i \neq j,有

dp(i,j) = \frac{1} {p + 1} \sum_{(j,k) \in E} {dp(trans(i,j),k) + 1}

由于聪聪和可可的距离是严格递减的,故状态不会直接或间接地转移到自己,可以保证这个转移是没有后效性的。于是记忆化搜索一下即可。时间复杂度O(n ^ 2)