简单概率dp(期望)-hdu-3853-LOOPS

发布时间:2016-12-11 16:11:14 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"简单概率dp(期望)-hdu-3853-LOOPS",主要涉及到简单概率dp(期望)-hdu-3853-LOOPS方面的内容,对于简单概率dp(期望)-hdu-3853-LOOPS感兴趣的同学可以参考一下。

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3853 题目大意: 给一个r*c的矩阵,每个格子(x,y),用2魔法值就可以走一步,(可以到(x,y)、(x+1,y)、(x,y+1)),告诉每个格子的能到达的三个位置的概率,求从左上角到达右下角所需魔法值的期望。 解题思路: 简单期望dp. dp[i][j]表示从位置(i,j)到达终点的期望,则dp[i][j]=(2+dp[i][j])*sa[i][j][0]+(2+dp[i][j+1])*sa[i][j][1]+(2+dp[i+1][j])*sa[i][j][2],移向即可得转移方程。 注意有除法,去掉分母为0的情况。 代码: #include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #define eps 1e-6 #define INF 0x3fffffff #define PI acos(-1.0) #define ll __int64 #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define Maxn 1100 double dp[Maxn][Maxn]; double sa[Maxn][Maxn][3]; int row,col; int main() { while(~scanf("%d%d",&row,&col)) { for(int i=1;i<=row;i++) for(int j=1;j<=col;j++) for(int k=0;k<3;k++) scanf("%lf",&sa[i][j][k]);//三种概率 dp[row][col]=0;//最后一格 往前递推 for(int i=row;i>=1;i--) for(int j=col;j>=1;j--) { if(i==row&&j==col) continue; if(fabs(1-sa[i][j][0])<eps) //不能从这里走,置为无效状态 { //wa了几发 dp[i][j]=INF; continue; } dp[i][j]=(2+dp[i][j+1]*sa[i][j][1]+dp[i+1][j]*sa[i][j][2])/(1-sa[i][j][0]); } printf("%.3f\n",dp[1][1]); } return 0; }

上一篇:C学习——指针
下一篇:[放松一下] 经典高清电影合集 170G BT种子下载

相关文章

相关评论