概率期望

poj2151 简单题

时限：2000MS 内存限制：65536K
提交总数：10714 接受日期：4424

描述

组织编程竞赛并非易事。为了避免问题太难，主办方通常期望比赛结果满足以下两个条件：
1.所有团队至少解决一个问题。
2. 冠军（解决最多问题的团队之一）至少解决一定数量的问题。

现在主办方已经把比赛问题研究出来了，通过初赛的结果，主办方可以估算出某个团队能够成功解决某个问题的概率。

给定比赛问题 M 的数量、团队 T 的数量以及组织者期望冠军至少解决的问题 N 的数量。我们还假设团队 i 以概率 Pij （1 <= i <= T， 1<= j <= M） 求解问题 j。那么，你能计算出所有团队至少解决一个问题的概率，同时冠军团队解决至少 N 个问题的概率吗？

输入

输入由多个测试用例组成。每个测试用例的第一行包含三个整数 M （0 < M <= 30）、T （1 < T <= 1000） 和 N （0 < N <= M）。以下每条 T 行都包含 [0，1] 范围内的 M 浮点数。在这些 T 行中，第 i 行中的第 j 个数字只是 Pij。M = T = N = 0 的测试用例表示输入结束，不应进行处理。

输出

对于每个测试用例，请在单独的行中输出答案。结果应四舍五入到小数点后三位。

示例输入

2 2 2
0.9 0.9
1 0.9
0 0 0

示例输出

0.972

---

题解:

给出每个队伍$AC$每道题的概率
求的是满足任意队伍$AC$至少一道题冠军队伍至少$AC$ $N$道题的概率

设事件 $A$: 任意队伍$AC$至少一道题 概率为 $P(A)$
设事件 $B$: 冠军队伍至少$AC$ $N$道题 概率为 $P(B)$
答案即为 $P(AB)$
$P(A)$ 即为每个队伍都 $AC$ $k$ $(1<=k<=M\mathrm{即}k\ne 0)$ 道题的概率(都不爆零)
但是 $p(B)$ 为所有队伍中至少存在一个队伍 $AC$ 的题数大于 $N$
$P(A)$ 好说可以一个一个队伍的处理最后再相乘(因为每个队伍是独立的)
但是 $P(B)$ 的处理就很头疼了不知道这个冠军队伍是那个队伍也不知道有几个冠军队伍(可以有多个)
所以正难则反求 $\bar{B}$ 即所有队伍中 $AC$ 题数都小于 $k$ 的概率
即把答案变为求 $P(A)-P(A\bar{B})$ 可以画一下 $venny$ 图理解一下
$P(A\bar{B})$ 即为每个队伍 $AC$ 题数 $1<=k<=N-1$ 的概率
注意这儿不能 $P(A)-P(A\bar{B})$ 不能化为每个队伍 $AC$ 题数 $k>=N$
因为 $P(A),P(A\bar{B})$ 两项都涉及所有队伍都满足的事件而不是单个队伍之中(因为每个队伍是独立的)
将$B$转化为 $\bar{B}$ 也是因为这个吧?(我是蒟蒻)

然后就可以愉快的 $dp$ 了要求的是每个队伍 $AC$ 题数为 $k$ 的期望概率(在一个队伍中所求的概率是可以相加的)
这样用一个前缀和就可以求出一个区间的期望概率(概率的期望)了

期望具有线性性
而概率的期望可以把这个概率看作一个权值
这里引用一下:结合实际问题具体的讲，就是：现在我们想要求某个事件 $A$ 发生的概率 $P$，有 $n$ 种可能的情况会发生，第 $i$ 种情况里面发生 $A$ 的概率是 $P_i$。每种情况还有一个发生的概率，设为 $Q_i$。相当于是两层随机，先随机一种情况，一种情况里面是否发生 $A$ 又是随机的。
($p[i][j]$为第$i$个队伍第$j$道题$AC$的概率)
设$dp$状态为$f[i][j][k]:$第$i$个队伍考虑前$j$本书$AC$ $k$ 道的期望概率

$$f[i][j][k]=f[i][j-1][k-1]\ast p[i][j]=f[i][j-1][k]\ast (1-p[i][j])$$

初始化显然$f[i][0][0]=1$,$f[i][j][0]=\prod _1^{j}p[i][j]$
最后把每个队伍的$P(A)$和$P(A\bar{B})$乘起来相减就是答案

std:

#include 
using namespace std;
const int N = 1010,M = 33;
int n,m,r;
double p[N][M],f[N][M][M],s[N][M];
int main()
{

    while(scanf("%d%d%d",&m,&n,&r)&&m&&n&&r)
    {
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                scanf("%lf",&p[i][j]);
        for(int i = 1;i <= n;i++)
        {
            f[i][0][0] = 1;
            for(int j = 1;j <= m;j++)
                f[i][j][0] = f[i][j-1][0]*(1-p[i][j]);
        }

        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                for(int k = 1;k <= j;k++)
                    f[i][j][k] = f[i][j-1][k-1]*p[i][j] + f[i][j-1][k]*(1-p[i][j]);
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                s[i][j] = s[i][j-1] + f[i][m][j];
        double A = 1,B = 1;
        for(int i = 1;i <= n;i++)
            A *= s[i][m]-s[i][0],B *= s[i][r-1]-s[i][0];
        printf("%.3lf\n",A-B);
    }
    return 0;
}

• poj2151 简单题
•     描述
•     输入
•     输出
•     示例输入
•     示例输出
• 题解:
• std:

__EOF__