CF1267G Game Relics

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})\)。