/*题意：有一个迷宫r行m列,开始点在[1,1]现在要走到[r,c] 对于在点[x,y]可以打开一扇门走到[x+1,y]或者[x,y+1] 消耗2点魔力 问平均消耗多少魔力能走到[r,c] 分析：假设dp[i][j]表示在点[i,j]到达[r,c]所需要消耗的平均魔力(期望) 则从dp[i][j]可以到达: dp[i][j],dp[i+1,j],dp[i][j+1]; 对应概率分别为： p1,p2,p3 由E(aA+bB+cC...)=aEA+bEB+cEC+...//包含状态A,B,C的期望可以分解子期望求解 得到dp[i][j]=p1*dp[i][j]+p2*dp[i+1][j]+p3*dp[i][j+1]+2; */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <queue> #include <algorithm> #include <map> #include <cmath> #include <iomanip> #define INF 99999999 typedef long long LL; using namespace std; const int MAX=1000+10; int n,m; double dp[MAX][MAX],p[MAX][MAX][3]; int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j)scanf("%lf%lf%lf",&p[i][j][0],&p[i][j][1],&p[i][j][2]); } memset(dp,0,sizeof dp); for(int i=n;i>=1;--i){ for(int j=m;j>=1;--j){ if(i == n && j == m)continue; if(p[i][j][0] == 1.00)continue;//该点无路可走,期望值肯定为0(dp[i][j]=0) dp[i][j]=(p[i][j][1]*(dp[i][j+1])+p[i][j][2]*(dp[i+1][j])+2)/(1-p[i][j][0]); } } printf("%.3lf\n",dp[1][1]); } return 0; }

MySQL架构组成之物理文件组成,布布扣,bubuko.com