现在的位置: 首页 > 综合 > 正文

poj 2151 Check the difficulty of problems

2014年09月05日 ⁄ 综合 ⁄ 共 2752字 ⁄ 字号 评论关闭

首先说一下这道题时无意中发现的啊、、不知道怎么搞得啊他竟然出现在了我们训练计划中的查找法中了啊、、不过无所谓啊,做做也没有什么坏处啊、、、

一开始看题的时候理解错题意了啊,一开始我是这么算的啊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了啊。

Check the difficulty of problems
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 3929   Accepted: 1740

Description

Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms: 
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 input consists of several test cases. The first line of each test case contains three integers M (0 < M <= 30), T (1 < T <= 1000) and N (0 < N <= M). Each of the following T lines contains M floating-point numbers in the range of [0,1]. In these T lines,
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

For each test case, please output the answer in a separate line. The result should be rounded to three digits after the decimal point.

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;
}

抱歉!评论已关闭.