shoi2002专题

P1291 [SHOI2002]百事世界杯之旅 (期望)

题意: 中文不解释了 分析: 假设表示一共有n个球星,现在还剩k个未收集到,还需购买饮料的平均次数。 那么要求的就是 假设我们现在推到了,我们再买一瓶饮料,有两种可能性,一种是:我们买到了我们没有拥有的球员,那么剩下的子问题就是;如果买到了我们拥有的球员,那么剩下的子问题就是。然而我们任意买一个瓶盖,有的可能性买到我们没有的,有的可能性买到我们已经有的。所以这道题目的递推是就是: