hdu3853：LOOPS

题目大意：r*c个点，每个点有Aij的概率回到自己本身，Bij的概率向右一格，Cij的概率向下一格，求从(1,1)到(r,c)的期望步数。

题解：有了hdu4405的经验，从后往前推期望。那么，E(i,j)=E(i,j)*Aij+E(i,j+1)*Bij+E(i+1,j)*Cij+2，注意加上“又消耗了两点”，闪一下，变成E(i,j)=(E(i,j+1)*Bij+E(i+1,j)*Cij+2)/(1-Aij)，问题马上产生！！！当Aij=1怎么办呢？

注意到Aij=1时，走进这个格就再也走不出来。因此你可以把到(i,j)的期望置0。这样，在计算期望的时候若用到这个点，可以当它不存在，不存在从到达这个点的情形。

它让你烦躁，为何不忽视它？

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 int n,m;

 #define maxn 1011

 #define eps 1e-9

 double E[maxn][maxn],A[maxn][maxn],B[maxn][maxn],C[maxn][maxn];

 int main()

 {

     while (scanf("%d%d",&n,&m)==)

     {

         for (int i=;i<=n;i++) for (int j=;j<=m;j++)

             scanf("%lf%lf%lf",&A[i][j],&B[i][j],&C[i][j]);

         E[n][m]=0.0;

         for (int i=n;i>;i--) for (int j=m;j>;j--)

         {

             if (i==n && j==m) continue;

             if (fabs(A[i][j]-)<eps) continue;

             E[i][j]=(B[i][j]*E[i][j+]+C[i][j]*E[i+][j]+2.0)/(-A[i][j]);

         }

         printf("%.3lf\n",E[][]);

     }

     return ;

 }

巴特西

hdu3853：LOOPS

最新文章

热门文章