首页 > 代码库 > HDU 3853LOOPS
HDU 3853LOOPS
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了~~~
1 //#pragma comment(linker,"/STACK:102400000,102400000") 2 #include <map> 3 #include <set> 4 #include <stack> 5 #include <queue> 6 #include <cmath> 7 #include <ctime> 8 #include <vector> 9 #include <cstdio>10 #include <cctype>11 #include <cstring>12 #include <cstdlib>13 #include <iostream>14 #include <algorithm>15 using namespace std;16 #define INF 1e917 #define inf (-((LL)1<<40))18 #define lson k<<1, L, mid19 #define rson k<<1|1, mid+1, R20 #define mem0(a) memset(a,0,sizeof(a))21 #define mem1(a) memset(a,-1,sizeof(a))22 #define mem(a, b) memset(a, b, sizeof(a))23 #define FOPENIN(IN) freopen(IN, "r", stdin)24 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)25 26 //typedef __int64 LL;27 //typedef long long LL;28 const int MAXN = 1005;29 const int MAXM = 100005;30 const double eps = 1e-13;31 //const LL MOD = 1000000007;32 33 double p1[MAXN][MAXN], p2[MAXN][MAXN], p3[MAXN][MAXN], dp[MAXN][MAXN];34 35 int main()36 {37 int R, C;38 while(~scanf("%d %d", &R, &C))39 {40 for(int i=1;i<=R;i++)41 for(int j=1;j<=C;j++)42 scanf("%lf%lf%lf", &p1[i][j], &p2[i][j], &p3[i][j]);43 mem0(dp);44 for(int i=R;i>=1;i--)45 for(int j=C;j>=1;j--)46 {47 if(i==R && j==C) continue;48 if(fabs(p1[i][j] - 1) < eps) continue;49 dp[i][j] = (dp[i][j+1]*p2[i][j] + dp[i+1][j]*p3[i][j] + 2) / (1-p1[i][j]) ;50 }51 printf("%.3lf\n", dp[1][1]);52 }53 return 0;54 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。