HDU 3853 LOOPS 概率dp入门 (1)

[cpp] view plaincopyprint?
<pre name="code" class="cpp">/**
*   Author : johnsondu
*   time: 2012-10-13-9:30 around
*   url: http://acm.hdu.edu.cn/showproblem.php?pid=3853
*   stratege: 概率dp
**/ 
#include <iostream> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
#include <cstring> 
using namespace std ; 
 
#define eps 1e-10 
#define M 1005 
double dp[M][M] ; 
double p[M][M][3] ;  // 三维,因为每个当前位置有3种走法(当前位置[r][c]),[r][c], [r+1][c], [r][c+1] ; 
int r, c ; 
 
double Abs (double t) 
{ 
    return t < 0 ? -t : t ; 
} 
 
 
int main () 
{ 
    int i, j, k ; 
    while (scanf ("%d%d", &r, &c) != EOF) 
    { 
        for (i = 0; i < r; i ++) 
            for (j = 0; j < c; j ++) 
            { 
                for (k = 0; k < 3; k ++) 
                    scanf ("%lf", &p[i][j][k]) ; //0--[r][c],  1--[r][c+1], 2--[r+1][c] 
                dp[i][j] = 0 ; 
            } 
        //dp[i][j] = p[i][j][0]*dp[i][j] + p[i][j][1] * dp[i][j+1] + p[i][j][2]*dp[i+1][j] + 2 
        // -->  dp[i][j] = (p[i][j][1] * dp[i][j+1] + dp[i+1][j]*p[i][j][2] + 2) / (1-p[i][j][0]) 
        // 注意: 1-p[i][j][0] > 0 ; 
        for (i = r-1; i >= 0; i --) 
            for (j = c-1; j >= 0; j --) 
            { 
                if (i == r-1 && j == c-1) continue ; 
                if (Abs (1-p[i][j][0] < eps)) continue ; 
                dp[i][j] = (p[i][j][1] * dp[i][j+1] + dp[i+1][j]*p[i][j][2] + 2) / (1-p[i][j][0])  ; 
            } 
        printf ("%.3lf\n", dp[0][0]) ; 
    } 
    return 0 ; 
} 
</pre><br> 
<br> 
<pre></pre> 

补充：软件开发 , C++ ,