[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>
