AC. 梦想

frank_c1

[BZOJ 2784] 时间流逝

发布于2017年01月22日 | 暂无评论 | 394阅读 | 动态规划

题意简述

n种能量圈,第i种能量是a_i。开始你没有能量圈。对于每一天,你有p的概率失去一个能量最小的能量圈,有1-p的概率可以等概率得到一个能量不大于你现有最小能量圈的能量圈。如果你现在没有能量圈,则不存在概率失去能量圈。

求第一次能量总和超过T的期望天数。

1 \le n \le 30, 1 \le T \le 50, 0.1 \le p \le 0.9

算法讨论

考虑如果我们知道如何表示一个状态,则不妨设其为x

E_xx达到终态的期望步数。有

E_x = (1 - p) \frac{1} {|next(x)|} \sum_{v \in next(x)} {E_v} + p E_{lst(x)} + 1

特殊地,对于初始状态有

E_{init} = \frac{1} {|next(x)|} \sum_{v \in next(init)} {E_v} + 1

高斯消元显然可以解决,但是复杂度过高。我们考虑深入挖掘问题的性质。

仔细观察式子,我们发现,对于一个状态x,至多有一个状态lst(x)是它的前驱,且存在状态init没有前驱。这是一棵树!一个状态的期望仅和它的儿子和父亲有关。

于是我们如果从叶子节点推起,就可以将一个结点的期望化简成E_x = a E_{lst(x)} + b的形式。一直推到根结点就得到了答案。

所有只有如何表示状态的问题啦。

考虑到naive的状态表示,就是把每一次得到的能量圈记录下来。我们发现这样其实是可行的,因为有效的状态中能量圈的能量之和必定不超过T,而50的正整数拆分数约为200000,是可承受的。

时间复杂度O(S(T))