【题解】BZOJ 1426 收集邮票

请注意,本文编写于 113 天前,最后修改于 113 天前,其中某些信息可能已经过时。

Problem

有 $n$ 种不同的邮票,每次只能买一张,每种概率 $\frac{1}{n}$ ,第 $k$ 张邮票花 $k$ 元,求集齐所有种类邮票的期望

Thought

已有 $x$ 张,集齐 $n$ 种邮票的期望张数

$$ g[x]=\frac{x}{n}g[x]+\frac{n-x}{n}g[x+1]+1\\ $$

但是这个东西好像并不能帮助我们去计算期望的费用...
因为权值不相同...(每一张费用相同不就是 sb 题了么

那么写个很 naive 的式子出来:

$$ f[i][j]=\frac{i}{n}f[i][j+1]+\frac{n-i}{n}f[i+1][j+1]+j+1 $$

其中 $f[i][j]$ 表示现在有 $i$ 种邮票,共 $j$ 张,得到 $n$ 种邮票的期望

同时, $f[i][j]$ 还能这么写:

$$ f[i][j]=\sum_{k=0}^{\infty}((j+1)+(j+2)+\cdots+(j+k))P(k,i) $$

其中, $P(k,i)$ 表示已有 $i$ 种,买 $k$ 张恰好得到 $n$ 种的概率

发现 $f[i][j+1]-f[i][j]$ 相当于等差数列求和,即

$$ f[i][j+1]-f[i][j]=\sum_{k=0}^{\infty}(1+2+\cdots+k)P(k,i) $$

这东西,不就是 $g[i]$ 么...

$$ g[i]=\sum_{k=0}^{\infty}(1+2+\cdots+k)P(k,i) $$

同时,$g[i]$ 显然是可以递推算出来的...

考虑用这个式子优化之前的转移方程

$$ f[i][j]=\frac{i}{n}(f[i][j]+g[i])+\frac{n-i}{n}(f[i+1][j]+g[i+1])+j+1 $$

所以说 $[j]$ 这一维就被优化掉了???

因为我们只需要求 $f[0][0] $,那么只考虑 $j=0$ 的情况

$$ f[i]=\frac{i}{n}(f[i]+g[i])+\frac{n-i}{n}(f[i+1]+g[i+1])+1 $$

就可以写出一个很简单的递推式了(具体是啥就不写了...

总结

当选择的代价和次数相关时,考虑两个代价之间的关系,往往会有意想不到的收获

Code

#include <bits/stdc++.h>
using namespace std;
int n;
double f[10005],g[10005];
int main() {
    scanf("%d",&n);
    for(int i=n-1;~i;--i) {
        g[i]=g[i+1]+(1.0*n)/(1.0*(n-i));
        f[i]=(1.0*i)/(1.0*(n-i))*(g[i]+1)+f[i+1]+g[i+1]+1;
    }
    printf("%.2lf\n",f[0]);
    return 0;
}
Comments

添加新评论