首先说一下这道题时无意中发现的啊、、不知道怎么搞得啊他竟然出现在了我们训练计划中的查找法中了啊、、不过无所谓啊,做做也没有什么坏处啊、、、
一开始看题的时候理解错题意了啊,一开始我是这么算的啊P1 = (1 - (1-0.9)*(1-0.9)) * (1-(1-1)(1-0.9)); P2 = 1- (1-(0.9 * 0.9)) * (1-(1*0.9));P1*P2 = 0.97119与答案不一致啊,一看disuss竟然有一样的错误啊、、感觉见到亲人了啊,呵呵、、后来看到有人提示的说他们不是独立事件就明白了啊、、不能直接相乘啊、、(哎,这个概率学的不好啊,下学期的概率论一定得好好听课啊、、)后来学习了别人的思路、、下面简述一下我的理解:
我们首先得求出1到N每种情况出现的概率,因为他们不是独立的都有联系的。所以用所有>=1的概率减去1到N之间(1<=x<n)的概率就是Pn的概率啊。
因为每个情况不是独立的,是有联系的,所以就会发现他们的状态方程式、g[i][j][k] = g[i][j -1][k -1] * (f[i][j]) + g[i][j -1][k] * (1- f[i][j]); g代表的是第几个队答了几道题对了几道,(队i,总题数j, 答对的k),我们知道当前答对的题目数有之前的状态决定啊、比如说:第一队在第3次答题的时候答对2到题的概率由两种情况的概率来决定(1)前2次就答对了2道题,此时第3次就得答错了,所以是g[i][j -1][k] * (1- f[i][j]);(2)前两次答对1道,则第三次就是必须答对啊所以是 g[i][j
-1][k -1] * (f[i][j]) ;那他们的概率就是g[i][j][k] = g[i][j -1][k -1] * (f[i][j]) + g[i][j -1][k] * (1- f[i][j]);
只要推出了转移方程再算出所有的和再减去1到n-1的概率就OK了啊。
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 3929 | Accepted: 1740 |
Description
1. All of the teams solve at least one problem.
2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems.
Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem.
Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you
calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems?
Input
the j-th number in the i-th line is just Pij. A test case of M = T = N = 0 indicates the end of input, and should not be processed.
Output
Sample Input
2 2 2 0.9 0.9 1 0.9 0 0 0
Sample Output
0.972
#include <stdio.h> #include <string.h> #include <iostream> using namespace std; double f[1010][50], g[1010][50][50]; int main() { int n, t, m; int i, j, k; double sum, ans, team; while(~scanf("%d %d %d",&n, &t, &m)) { if(n == m && m == t && t == 0) break; for(i = 0; i < t; i++) for(j = 1; j <= n; j++) scanf("%lf",&f[i][j]); memset(g , 0 , sizeof(g)); for(i = 0; i < t; i++) { g[i][0][0] = 1; for(j = 1; j <= n; j++) { g[i][j][0] = g[i][j-1][0]*(1-f[i][j]); for(k = 1; k <= j; k++) g[i][j][k] = g[i][j-1][k]*(1-f[i][j]) + g[i][j-1][k-1]*f[i][j]; } } ans = 1.0; for(i = 0; i < t; i++) ans *= 1-g[i][n][0]; team = 1.0; for(i = 0; i < t; i++) { sum = 0; for(j = 1; j < m; j++) sum += g[i][n][j]; team *= sum; } ans -= team; printf("%.3lf\n",ans); } return 0; }