HDU 3853LOOPS(简单概率DP)

时间：2021-12-09 16:26:27

HDU 3853    LOOPS

题目大意是说人现在在1,1,需要走到N,N，每次有p1的可能在元位置不变，p2的可能走到右边一格，有p3的可能走到下面一格，问从起点走到终点的期望值

这是弱菜做的第一道概率DP的题，首先是看了一下有关概率DP的资料，大概知道一般球概率就是从起点推到终点，求期望就是从终点推到起点

考虑这题的做法，其实很简单设DP[i][j]表示从i，j到达终点所需时间的期望值

　　DP[i][j] =p1 *  DP[i][j] + p2 * DP[i][j+1] + p3 * DP[i+1][j] + 1

最后需要+1是因为转移到下一秒的状态需要一秒，然后就愉快的AC了～～～

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e9

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 double p1[MAXN][MAXN], p2[MAXN][MAXN], p3[MAXN][MAXN], dp[MAXN][MAXN];

 int main()

 {

     int R, C;

     while(~scanf("%d %d", &R, &C))

     {

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

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

                 scanf("%lf%lf%lf", &p1[i][j], &p2[i][j], &p3[i][j]);

         mem0(dp);

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

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

             {

                 if(i==R && j==C) continue;

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

                 dp[i][j] = (dp[i][j+]*p2[i][j] + dp[i+][j]*p3[i][j] + ) / (-p1[i][j]) ;

             }

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

     }

     return ;

 }

相关文章