【BZOJ1426】收集邮票 期望DP

题目大意

　　有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票（注意是第k张而不是第k种）需要支付k元钱。现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

　　n≤10000

题外话

　　如果买第k种需要k元钱要怎么做？

　　已经买了i张，买到下一张需要的期望钱数是nn?i×n+12

　　所以总的代价是
∑i=0n?1n(n+1)2(n?i)=n(n+1)2∑i=1n1i
　　可惜这题没那么简单。

题解

　　设p(x,i)为已经买了i个物品，通过x次购买买完剩下的物品的概率

　　设gi为已经买到了i个物品，买完所有物品的期望次数
gi=gi+1+nn?i
　　下一次买到想要的物品的概率为n?in，取倒数就是期望

　　还有一条式子
gi=∑x=1∞x×p(x,i)
　　买x次成功的概率乘以x

　　设fi,j为已经买到了i个物品，之间买过j次，买完所有物品的花费

　　有一个递推式
fi,j=fi,j+1×in+fi+1,j+1×n?in+(j+1)

fi,j=∑x=1∞((j+1)+(j+2)+?(j+x))×p(x,i)=∑x=1∞x(x+2j+1)2×p(x,i)

　　作差得
fi,j+1?fi,j=∑x=1∞x×p(x,i)=gifi,j+1=fi,j+gi
　　代入到递推式中得
fi,jfi,jfi,j=(fi,j+gi)×in+(fi+1,j+gi+1)×n?in+(j+1)=infi,j+ingi+n?infi+1,j+n?ingi+1+(j+1)=in?igi+fi+1,j+gi+1+nn?i(j+1)
　　可以发现fi,j只和j，fi+1,j，gi，gi+1有关。因为我们只要求f0,0，所以可以把j那一维删去
fi=in?igi+fi+1+gi+1+nn?i

代码

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair pii;
double g[100010];
double f[100010];
int main()
{
    int n;
    scanf("%d",&n);
    int i;
    g[n]=0;
    for(i=n-1;i>=0;i--)
        g[i]=g[i+1]+double(n)/(n-i);
    f[n]=0;
    for(i=n-1;i>=0;i--)
        f[i]=f[i+1]+double(i)/(n-i)*g[i]+g[i+1]+double(n)/(n-i);
    printf("%.2lf\n",f[0]);
    return 0;
}