POJ2151 동적 계획

 1 #include <iostream>

 2 #include <cstring>

 3 #include <cstdio>

 4 

 5 using namespace std;

 6 

 7 int m, t, n;

 8 double dp[1005][40][40];

 9 double p[1005][40];

10 double p1, p2;

11 

12 int main()

13 {

14     while (scanf("%d%d%d", &m, &t, &n) && m) { //   &&   &，wa 1   

15         memset(dp, 0, sizeof(dp));

16         for (int i = 1; i <= t; i++) {

17             for (int j = 1; j <= m; j++) 

18                 scanf("%lf", &p[i][j]);

19         }

20 

21         for (int i = 1; i <= t; i++) {

22             

23             dp[i][0][0] = 1.0;

24             for (int j = 1; j <= m; j++) {

25                 dp[i][j][0] = dp[i][j - 1][0] * (1 - p[i][j]);

26             

27                 for (int l = 1; l <= j; l++) {

28                     dp[i][j][l] = dp[i][j - 1][l] * (1 - p[i][j]) 

29                                 + dp[i][j - 1][l - 1] * p[i][j];    

30                 }

31             }

32         }

33 

34         double s1 = 1;

35         double s2 = 1;

36         

37         for (int i = 1; i <= t; i++) {

38             p1 = 0;

39             for (int j = 1; j < n; j++) 

40                 p1 += dp[i][m][j];

41             s1 *= p1;

42         }

43 

44         

45         for (int i = 1; i <= t; i++) {

46             p2 = 1 - dp[i][m][0];

47             s2 *= p2;

48         }

49         printf("%.3lf
", s2 - s1);

50     }

51     return 0;

52 }