LOOPS HDU - 3853 

题意:从(1,1)出发,每次只能有p1,p2,p3的概率原地不动,向右走一步,向下走一步,问走到(n,m)期望步数*2的答案是多少

思路:

定义:dp[i][j] 为(i,j)出发的期望

移项

分母不为0,即当p1为1时,dp[n][m]=0.0  ,   实际意义就是,如果到了这点只能原地打转,那么这个点的状态不能去影响其他点,即赋值为0.0

#include<cstdio>
#include<vector>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e3+3;
const int MOD=1e9+7;
const double EPS=1e-12;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
int sign(double x){
    return fabs(x) < EPS ? 0 : x>0 ? 1 : -1 ;
}
double a[1005][1005][4];
double dp[1005][1005];
int n,m;

void mian(){
    for(int i=1;i<=1000;i++)
        for(int j=1;j<=1000;j++)    dp[i][j]=0.0;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=3;k++)   sf(a[i][j][k]);

    for(int i=n;i>=1;--i){
        for(int j=m;j>=1;--j){
            if(i==n&&j==m)  continue;
            if(sign(a[i][j][1]-1)==0)   continue;
            double p1=a[i][j][1];
            double p2=a[i][j][2];
            double p3=a[i][j][3];
            dp[i][j]=(p2*dp[i][j+1]+p3*dp[i+1][j]+2)/(1-p1);
        }
    }
    printf("%.3f\n",dp[1][1]);
}
int main(void){
    while(scanf("%d%d",&n,&m)==2){
        mian();
    }

    return 0;
}