poj 2151(概率DP)

poj 2151
设$dp(i, j, k)$为选手$i$在前$j$题中做对$k$题的概率,则转移方程为
$$dp(i,j,k)=dp(i,j-1,k-1) \times p(i,j) + dp(i,j-1,k) \times (1-p(i,j))$$
初始化的时候$dp(i,0,0)=1, dp(i,j,0)=dp(i,j-1,0) \times (1-p(i,j))$
然后因为我们要求出所有选手做对一题且有选手做出大于等于$n$题,所以这是个容斥问题,即可以用所有选手至少做对一题的概率$P_1$减去所有选手做对题目个数在$[1, n-1]$之间的概率$P_2$的差即为答案,怎么求呢?
设$s(i,j)$为选手$i$做对至多$j$题的概率,则$s(i,j)= \sum_{k=0}^{j} dp(i, k)$
则$P_1= \prod_{i=1}^{t}(1-s(m, 0)) $
$P_2= \prod_{i=1}^{t}(s(m, n-1)-s(m, 0)) $
$P_1 - P_2$即为答案(容斥原理)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXM = 50 + 5, MAXT = 1000 + 10;
int m, t, n;
db p[MAXT][MAXM], dp[MAXT][MAXM][MAXM], s[MAXT][MAXM];
void clean() {
ms(dp, 0);
}
void solve() {
clean();
for (int i=1;i<=t;i++)
for (int j=1;j<=m;j++) scanf("%lf", &p[i][j]);
for (int i=1;i<=t;i++) {
dp[i][0][0] = 1;
for (int j=1;j<=m;j++) dp[i][j][0] = dp[i][j-1][0] * (1 - p[i][j]);
for (int j=1;j<=m;j++) {
for (int k=1;k<=j;k++) {
dp[i][j][k] = dp[i][j-1][k-1] * p[i][j] + dp[i][j-1][k] * (1 - p[i][j]);
}
}
}
for (int i=1;i<=t;i++) {
s[i][0] = 0;
for (int j=0;j<=m;j++) s[i][j] = s[i][j - 1] + dp[i][m][j];
}
db p1 = 1, p2 = 1;
for (int i=1;i<=t;i++) p1 *= (1 - s[i][0]);
for (int i=1;i<=t;i++) p2 *= (s[i][n-1] - s[i][0]);
printf("%.3f\n", p1 - p2);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d%d", &m, &t, &n)&&(m||t||n)) solve();
fclose(stdin); fclose(stdout);
return 0;
}
------ 本文结束 ------