期望的意义就是对于做一件事情,期望多少次这件事情可以做成功.
"......在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字.只要凑齐所有百事球星的名字,就可参加百事世界杯之旅的抽奖活动,获得球星背包,随声听,更克赴日韩观看世界杯.还不赶快行动!"
你关上电视,心想:假设有n个不同的球星名字,每个名字出现的概率相同,平均需要买几瓶饮料才能凑齐所有的名字呢?
首先定义转移状态$f[i]$为收集到$i$个不同的球星的期望要买多少个.则$f[i]$这个状态可以从两个状态转移过来,一种是对于$f[i - 1]$这种状态买了不同的一个球星,另外一种就是$f[i]$,但是买的和原来的一样.
所以我们可以粗略的得到以下的转移方程:
所以我们要重新考虑这样做的意义何在:
由于对于这这道题而言,当购买结束后,就不需要购买,那么我们可以略微修改一下转移方程的意义:"买了一个,买的是自己又的的概率" ==" "买一个,买的是自己有的且不是自己的概率"
那么这样的转换就可以消去多余的$\frac{1}{n}$
从而,我们可以得到正确的转移方程:
最后进行以下化简,然后简单地$dp$就可以了.最后,这道题需要考虑分数线等神奇的情况,此为题目细节,这里不过多赘述.下面为$AC$代码:
著名的电子产品品牌SHOI 刚刚发布了引领世界潮流的下一代电子产品 -  -  概率充电器:
"采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决 定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看 吧!"
SHOI 概率充电器由n-1 条导线连通了n 个充电元件.进行充电时,每条导 线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概率 决定.随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行 间接充电.
作为SHOI 公司的忠实客户,你无法抑制自己购买SHOI 产品的冲动.在排 了一个星期的长队之后终于入手了最新型号的SHOI 概率充电器.你迫不及待 地将SHOI 概率充电器插入电源 -  - 这时你突然想知道,进入充电状态的元件 个数的期望是多少呢?
第一行一个整数:n.概率充电器的充电元件个数.充电元件由1-n 编号.
之后的n-1 行每行三个整数a b p,描述了一根导线连接了编号为a 和b 的 充电元件,通电概率为p%.
第n+2 行n 个整数:qi.表示i 号元件直接充电的概率为qi%.
所以可以得出题目的所求:
那么我们只需要列出方程,然后两边$dfs$就可以非常顺利地A掉这道题.
接下来,是第二遍自上而下的$dfs$的转移方程:
知乎 | 你的导师对你说过什么让你至今难以忘怀的话?