JLOI2012 时间流逝

Link

题意

有$n$种宝⽯,第$i$种的能量是$a_i$。开始你没有任何宝⽯。 每⼀天你有$p$的概率失去⼀个能量最小的宝⽯, 否则可以在所有能量不超过你拥有的任何⼀个宝⽯的宝⽯中等概率随机获得⼀个。 每种宝石有无限多个。如果某⼀天你没有宝⽯,则不存在概率失去宝⽯。 求第⼀次宝⽯的能量总和超过 $T$ 的期望天数

数据范围:$0\leq T, n\leq 50; 0.1 \leq p \leq 0.9$

题解

很神的题,我不会做。膜了这篇题解

设$E_S$表示状态为$S$的时候到达目标状态的期望步数。
$$
E_S = 1 + p\times E_{last(S)}+(1-p)\frac{1}{|next(S)|}\times \sum E_{next(S)}
$$
其中$last(S)$指状态$S$删去最小宝石以后的状态,$next(S)$指状态$S$得到一个宝石以后的状态。

如果把$last(S)$看成$S$的父亲,$next(S)$看成$S$的儿子,那么可以把这个转移看成一个转移树。

你会发现点$S$能从儿子转移也能从父亲转移。

这个时候要用到一个叫树上高斯消元的trick。(noi前在雅礼听过但是并不会

我们假设已知$S$子树的DP值。
$$
E_S = p\times E_{last(S)}+[(1-p)\frac{1}{|next(S)|}\times \sum E_{next(S)} + 1]\\
E_s = kE_{last(S)}+b
$$
那么可以把$E_s$的DP值用$E_{last(S)}$表示

所以我们可以假设
$$
E_{next(S)}=kE_{S}+b
$$
带入原式:
$$
E_S = 1 + p E_{last(S)}+(1-p)\frac{1}{|next(S)|}\times \sum (kE_{S}+b)\\
\text{let}~~G = (1-p)\frac{1}{|next(S)|}\\
(1-G\sum k)E_s = 1+p E_{last(S)}+G\sum b\\
E_s=\frac{p}{1-G\sum k}E_{last(S)} + \frac{1 + G \sum b}{1-G \sum k}\\
E_s = newk \times E_{last(S)}+newb
$$
特殊的
$$
\text{if}~~sumv > T~~~~E_s = 0
$$
对于最顶端,没有$Last(S)$,此时的$b$就是答案。

代码

Leave a Reply

Your email address will not be published. Required fields are marked *