[P4550] 收集邮票 - 概率期望,dp

2024-10-08 08:06:39

套路性地倒过来考虑，设\(f[i]\)表示拥有了\(i\)种票子时还需要多少次购买，\(g[i]\)表示还需要多少钱

推\(g[i]\)递推式时注意把代价倒过来（反正总数一定，从顺序第\(1\)张开始加钱和倒序没有区别）

#include <bits/stdc++.h>

using namespace std;

const int N = 10005;

double f[N],g[N];

int n;

int main() {

    cin>>n;

    for(int i=n-1;i>=0;--i) {

        f[i]=f[i+1]+1.0*n/(n-i);

    }

    for(int i=n-1;i>=0;--i) {

        g[i]=1.0*i/(n-i)*(f[i]+1)+g[i+1]+f[i+1]+1;

    }

    printf("%.2lf\n",g[0]);

}

最新文章

热门文章