题意

有 \(k\) 种装备,一开始每种装备各有一个,且每种装备的初始等级均为 \(1\) 。游戏中可以靠打怪来获取新装备,总共有 \(n\) 只怪兽,每打赢一只怪兽后会随机获得一种装备,假设原有的 \(a\) 装备的等级为 \(t\) ,那么新获得的装备的等级为 \([1,t+1]\) 中随机一个,每次将等级较低的装备卖出,卖出可获得的金币为该装备的等级。 求打完多有怪兽以后可以获得的金币期望。

分析

考虑 \(O(n^2)\) 的dp是显然的。

每个武器是可以分开考虑的,我们仅针对一个武器考虑。

\(f[i][j]\) 表示到第 \(i\) 个怪兽,当前等级为 \(j\) 可以获得的金币期望。

考虑三种情况:

  • \(\frac{k-1}{k}\) 的概率取不到这种武器,此时 \(f[i][j]=f[i-1][j]\) ;
  • \(\frac{1}{k}\cdot \frac{1}{j+1}\) 的概率,可以使得武器升级 \(f[i][j+1]=(f[i][j]+j)*p\)
  • \(\frac{1}{k}\cdot \frac{j}{j+1}\) 的概率,可以使得武器不会升级,可以利用等差数列求和,一起求出来。

但是,复杂度怎么优化。

我们可以发现当 \(j\) 很大的时候,取到的概率很小,由于精度,甚至可以忽略不计。

于是当 \(j>600\) 的时候,我们不再处理,这样就能保证复杂度是正确的。

内存比较紧,开滚动数组。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注