HDU 3853 LOOPS：期望dp【网格型】

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3853

题意：

　　有一个n*m的网格。

　　给出在每个格子时：留在原地、向右走一格，向下走一格的概率。

　　每走一格会消耗2点体力。

　　问你从(1,1)到达终点(n,m)消耗体力的期望。

题解：

　　表示状态：

　　　　dp[i][j] = rest steps（剩余路程花费体力的期望）

　　　　i,j：现在的位置

　　找出答案：

　　　　ans = dp[0][0]

　　如何转移：

　　　　期望dp的套路：考虑子期望。。。

　　　　now: dp[i][j]

　　　　能转移到的子期望：dp[i][j]（留在原地）,dp[i][j+1]（向右）,dp[i+1][j]（向下）

　　　　dp[i][j] = dp[i][j]*trans[i][j][0]

　　　　　　　　　　+ ( dp[i][j+1]*trans[i][j][1]

　　　　　　　　　　　　+ dp[i+1][j]*trans[i][j][2] + 2 )

　　　　移项：

　　　　dp[i][j] = ( dp[i][j+1]*trans[i][j][1]

　　　　　　　　　　　　+ dp[i+1][j]*trans[i][j][2] + 2 )

　　　　　　　　　　/ (1-trans[i][j][0])

　　边界条件：

　　　　dp[n-1][m-1] = 0

　　　　到达终点后不用再耗体力。

　　注：（1）对于所有越界的概率应看成0。

　　　　（2）除法要保证除数不为0。

AC Code:

 // state expression:

 // dp[i][j] = rest steps

 // i,j: present pos

 //

 // find the answer:

 // ans = dp[0][0]

 //

 // transferring:

 // now: dp[i][j] -> dp[i][j], dp[i+1][j], dp[i][j+1]

 // dp[i][j] = dp[i][j]*trans[i][j][0]

 //            + (dp[i][j+1]*trans[i][j][1]

 //                + dp[i+1][j]*trans[i][j][2] + 2)

 // dp[i][j] = (dp[i][j+1]*trans[i][j][1]

 //                + dp[i+1][j]*trans[i][j][2] + 2)

 //            / (1-trans[i][j][0])

 //

 // boundary:

 // dp[n-1][m-1] = 0

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 1005

 using namespace std;

 int n,m;

 double dp[MAX_N][MAX_N];

 double trans[MAX_N][MAX_N][];

 void read()

 {

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

     {

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

         {

             for(int k=;k<;k++)

             {

                 scanf("%lf",&trans[i][j][k]);

             }

         }

     }

 }

 void solve()

 {

     memset(dp,,sizeof(dp));

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

     {

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

         {

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

             if(trans[i][j][]==1.0) continue;

             dp[i][j]=(dp[i][j+]*trans[i][j][]+dp[i+][j]*trans[i][j][]+2.0)/(1.0-trans[i][j][]);

         }

     }

 }

 void print()

 {

     printf("%.3f\n",dp[][]);

 }

 int main()

 {

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

     {

         read();

         solve();

         print();

     }

 }

巴特西

HDU 3853 LOOPS：期望dp【网格型】

最新文章

热门文章