SGU 495-Kids and Prizes【期望DP】

深碍√TFBOYSˉ_ 2023-06-07 14:27 17阅读 0赞

题意：

有n个奖品，m个人排队来选礼物，对于每个人，他打开的盒子，可能有礼物，也有可能已经被之前的人取走了，然后把盒子放回原处。求最后m个人取走礼物的期望总数。

多组数据
保留9为小数

思路：f[i] 表示第i个人取走礼物的期望总数，那么对于f[i] 来说， 它有f[i - 1] / n 的概率取到一个空的，1 - f[i - 1] / n 的概率取到一个礼物，那么转移方程就是f[i] = f[i - 1] / n * f[i - 1] + (n - f[i - 1] ) / n * (f[i - 1] + 1)， 由于求得是期望，所以我们初始f[m] = 0, 目标状态是f[0].

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn = 1e5 +10;
  5. double f[maxn];
  7. int main()
  8. {
  9.     int n, m;
  10.     while(~scanf("%d%d", &n, &m))
  11.     {
  12.         for(int i = 0; i <= m + 2; ++i) f[i] = 0;
  13.         f[m] = 0;
  14.         for(int i = m - 1; i >= 0; --i)
  15.         {
  16.             f[i] = ((double)n - f[i + 1]) / n * (f[i + 1] + 1) + f[i + 1] / n * f[i + 1];
  17.         }
  18.         printf("%.10f\n", f[0]);
  19.     }
  20.     return 0;
  21. }

发表评论

表情：
评论列表 （有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

    相关 期望DP入门

    期望DP一般步骤： 1.模拟过程，找出线性性质，作为阶段（这本质上也是线性DP） 2.涉及DP状态 原则： 体现线性性质 体现边权 根据对期望有无贡献来设计状态

    雨点打透心脏的1/2处雨点打透心脏的1/2处/ 0 赞/ 161 阅读

    相关 HDU 3853-LOOPS【期望DP】

    题意：有一个R\C的迷宫，从（1,1）走到（R,C），每个格子给出停留在原地，向右走一格和向下走一格的概率，且每走一步需要2点能量，求最后所需要的能量期望。 题目链接：[ht

    小咪咪小咪咪/ 0 赞/ 113 阅读