题目传送门(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]);}