题目传送门(BZOJ)
>原文链接<

题解 :

设两个状态$F[i], G[i]$分别表示

  • 已经有了$i$种邮票,期望还需要买多少张。
  • 已经有了$i$种邮票,期望还需要花多少钱。

初始状态$F[n]=G[n]=0$

转移方程

  • $F[i] = F[i+1]+n/(n-i)$
  • $G[i] = G[i+1]+F[i+1]+F[i]*i/(n-i)+n/(n-i)$

转移$G[i]$时,可以当作从1元的邮票开始买,加$F[i+1]$代表后面的所有邮票都贵了一块钱。

代码 :

#include <cstdio>#define f2 doubleconst int N = 11000;f2 f[N], g[N];int main() { int n; scanf("%d", &n); for(int i = n-1; i >= 0; i -- ) f[i] = f[i+1]+(f2)n/(n-i); for(int i = n-1; i >= 0; i -- ) g[i] = g[i+1]+f[i+1]+f[i]*i/(n-i)+(f2)n/(n-i); printf("%.2f\n", g[0]);}