CF1267G Game Relics
有 \(n\) 个物品，你可以进行下面两种操作：
花费 \(c_i\) 元购买第 \(i\) 个物品。
花费 \(x\) 元抽奖，等概率随机获得一个物品 \(i\)。若你已经拥有第 \(i\) 个物品，则你本次抽奖的花费改为 \(\dfrac{x}{2}\) 元。
求获得所有物品的期望最小花费。
\(1 \leq n \leq 100\)，\(1 \leq x \leq c_i \leq 10000\)，\(\sum\limits_{i=1}^{n} c_i \leq 10000\)。
首先我们有如下的观察：
性质 \(1\)：如果选择抽奖，则会一直选择抽奖，直到抽到新的物品为止。
证明显然，考虑若抽奖在当前状态下是最优决策，则没有抽到新的物品时状态不变，继续抽奖仍然是最优决策。
此时我们不妨设已经拥有了 \(k\) 个物品，则抽到一个新物品的期望花费为 \(\sum\limits_{i=0}^{\infty} (\dfrac{k}{n})^i \times \dfrac{n-k}{n} \times (\dfrac{i}{2} + 1) \times x\)，经过计算可以化简为 \(\dfrac{x}{2} \times (1 + \dfrac{n}{n-k})\)。