k张k元不好做,先考虑每张都是1元怎么做.
设f[i]表示,已经有了i种,买到n种的期望步数,也就是期望花费.
因为这个f数组,可以表示期望的步数,非常有用.以下讲解继续沿用.
然后,对于k张k元的情况,有两种做法:
(都要通过 期望=概率*事件的结果取值 来理解)
设g[i]表示,从有了i种有邮票到买到n种邮票要花的钱数.
i/n是买到自己原来买过的概率.
该种情况下,到达的结果是,还要有的g[i]花费,并且,之后期望还要买的f[i]次价格都上涨了1,总体加了f[i],再加上这次的1花费.
为什么可以认为,这一次是第一次买,花费是1呢?
我们在状态中,默认已经有了i张(从天上掉下来的,不花钱),所以,第一次买就是1元了.
或者,因为我们最后要求的是g[0],
对于g[0],第一次买花费1肯定是成立的.
所以,我们之后的所有花费,都默认第一次是1,之后计算还会加上的.
画图理解一下,g[i]的组成,黑色部分是的g[i]红色一道是增加了总体的f[i] 绿色一个点是这次操作花费的1元.
而相邻的g[i+1]->g[i]的更新时类似的.因为都加上了一个f[i+1]么,所以g[i+1]的花费1也就变成了花费2了.
因为,E((x+1)^2)=E(x^2)+2E(x)+1
拆开括号,移项,然后直接求.
期望一定要小心谨慎分析,不要直觉瞎搞,设计好状态,转移.