CF623D birthday 贪心概率期望

题意：n个人，玩抓人游戏，每抓住一个人都要猜这个人是谁。对于每一局，第i个人有$p_{i}$的概率被抓到。游戏结束当且仅当每个人都在某局中被抓到并且猜中自己的名字，求一个合适的策略来使得期望游戏局数最少，输出这个期望最少局数.
题解：设$g[i]$表示到$i$局为止，已经全部被猜中过的概率，$f[i][x]$表示到第$i$局为止，已经猜中过第$x$个人的概率。
那么有$$ans = \sum_{i = 1}^{\infty} (g[i] - g[i - 1])i$$
随游戏局数增长，$g[x]$会趋近于1，要让期望最小，显然在$x$越小时，要让$g[x] - g[x - 1]$越大越好，即$g[x]$增长的越快越好。
若在第$i$局猜被抓到的是$k$，那么有：
$f[i][x] = \begin{cases}
f[i - 1][x] + (1 - f[i - 1][x]) p_{x} \quad x == k\\
f[i - 1][x] \quad x != k
\end{cases}$
$g[x] = g[x - 1] \frac{f[x][k]}{f[x - 1][k]}($因为只有$f[x][k]$变化了)
因此我们只需要让$\frac{f[x][k]}{f[x - 1][k]}$最大即可。
$$\frac{f[x][k]}{f[x - 1][k]} = \frac{f[x - 1][k] + (1 - f[x - 1][k])p_{k}}{f[x - 1][k]} = 1 + \frac{(1 - f[x - 1][k])p_{k}}{f[x - 1][k]}$$
所以要使$\frac{(1 - f[x - 1][k])p_{k}}{f[x - 1][k]}$最大。
因此我们枚举$k$,贪心的找最优策略并更新答案，大约$3e5$次可以满足精度要求

这里注意为了满足初始化的要求(在没有把n个人都猜过之前，是没有概率全部猜中的)，所以要在最开始先把n个人都猜一遍，然后再继续贪心

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 110

 #define ld double 

 int n;

 ld ans, last, g;

 ld f[AC], p[AC];

 inline int read()

 {

     int x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 ld cal(int x){

     return f[x] + 1.0 * ( - f[x]) * p[x];

 }

 void pre()

 {

     n = read(), last = ;

     for(R i = ; i <= n; i ++)

         f[i] = p[i] = 1.0 * read() / 100.0, last *= p[i];//根据转移式来的

     ans = n * last;//因为只有猜过所有人之后才有可能结束游戏。。。

 }

 /*        int x = 0; ld maxn = 0;

         for(R j = 1; j <= n; j ++)

         {

             ld now = cal(j);

             if(cal(j) / f[j] > maxn) maxn = now, x = j;

         }    */

 void work()//为了解决初始化问题，，，先把所有人都猜一遍

 {

     for(R i = n + ; i <= ; i ++)

     {

         int x = ; //x不能默认为1，不然f[x]就为0了，，，，

         for(R j = ; j <= n; j ++)

             if(cal(j) / f[j] > cal(x) / f[x]) x = j;

         g = last * cal(x) / f[x], f[x] = cal(x);

         ans += i * (g - last), last = g;

     }

     printf("%.10lf\n", ans);

 }

 int main()

 {

     freopen("in.in", "r", stdin);

     pre();

     work();

     fclose(stdin);

     return ;

 }

巴特西

CF623D birthday 贪心概率期望

最新文章

热门文章

巴特西

CF623D birthday 贪心 概率期望

最新文章

热门文章

CF623D birthday 贪心概率期望