Cyan's Blog

Description

有n个石子，A和B轮流做游戏，A先手，每次抛硬币，若正面朝上就拿走一枚石子，否则不作任何事。取到最后一颗石子的人胜利。AB都想取胜，A有p机率抛到想要的，B有q(p,q>=0.5)。求A获胜的概率。

Solution

设f[i]表示A为先手A赢的概率，g[i]为B为先手A赢的概率。

对于f[i]，显然从max(g[i],g[i-1])转移，g[i]类似，不过要从min转移。

那么有f[i]=p*g[i-1]+(1-p)*g[i],g[i-1]>g[i]

         g[i]=q*f[i-1]+(1-q)*f[i],f[i-1]<f[i]

讨论一下发现，若f[i-1]>g[i]那么f[i-1]<f[i]一定成立，反之亦然。

于是化简上面的式子得到

         f[i]=(p*g[i-1]+q*(1-p)*f[i-1])/(p+q-p*q);

Description

有n种不同的邮票，每一次买一张邮票，买到每种邮票的概率都是1/n，第k次买花费k元，求买齐n种不同的邮票需要的钱的期望。

Solution

设f[i]为目前有i种不同的邮票，到买完所有邮票还需要买的邮票数的期望(倒着考虑转移方便些>.<)。

考虑本次决策，显然有f[i]=(i/n)*f[i]+((n-i)/n)*f[i+1]+1。

移项化简得到，f[i]=f[i+1]+(n/(n-i))。

由于每次的花费不同，接着考虑，设g[i]为期望的钱数。

因为到达x局面时已经有期望次数f[x]，所以本次贡献为f[x]+1。

于是有g[i]=(i/n)*(g[i]+f[i]+1)+((n-i)/n)*(g[i+1]+f[i+1]+1)。

化简得到，g[i]=(i/(n-i))*f[i]+g[i+1]+f[i+1]+n/(n-i)。

通过dp愉快地解决了本题。