POJ 2151 Check the difficulty of problems

Posted on | In | 阅读

动态规划问题。需要使用动态规划求出下面几个值

p[i][j]: 队i完成j题的概率，是题目的输入

dp[i][j][k]: 队i在前j题中完成k题的概率

s[i][j]: 队i完成不多于j题的概率，dp[i][m][0~j]的累加

p1: 所有队都至少完成一题的概率，(1-s[i][0])累乘

p2: 所有队都做出1~n-1题的概率，(s[i][n-1]-s[i][0])累乘

显然，最终的结果是p1-p2

C++ Code

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
44
45
46
47
48
49
50
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>

#define M 32
#define T 1002

using namespace std;

double p[T][M]; // probability of team i solves problem j
double dp[T][M][M]; // probability of team i solves k of the first j problems
double s[T][M]; //probability of team i solves at most j problems
int main(){
    int m, t, n;
    while(scanf("%d%d%d", &m, &t, &n) && m != 0){
        memset(dp, 0, sizeof(dp));
        memset(s, 0, sizeof(s));
        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.0;
            for(int j = 1; j <= m; j++){
                dp[i][j][0] = dp[i][j-1][0] * (1 - p[i][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] = dp[i][m][0];
            for(int j = 1; j <= m; j++){
                s[i][j] = s[i][j-1] + dp[i][m][j];
            }
        }
        double p1 = 1.0;
        for(int i = 1; i <= t; i++){
            p1 *= (1-s[i][0]);
        }
        double p2 = 1.0;
        for(int i = 1; i <= t; i++){
            p2 *= (s[i][n-1] - s[i][0]);
        }
        printf("%.3f\n", p1-p2);
    }
    return 0;
}