HDU 3853 LOOPS (概率dp)

OJ 题目 ： click here ~~

大概题意 ：R *C的格子，起始点在（1，1），终点是（R ， C）。走一个点需要消耗2个能量。在（i ，j）时，可以以概率p1走到（i， j），仍在原地。以概率p2，走到（i，j+1 ）。以概率p3，走到（i+1 ，j）。问从起点到终点需要消耗的能量期望。

此题为概率dp的入门题，但是要注意，有除法，注意分母为0的情况。

AC_CODE

double dp[1002][1002];
const double eps = 1e-5;
struct Node
{
double p1;
double p2;
double p3;
Node(){}
Node(double i , double j , double k):p1(i),p2(j),p3(k){}
};
Node pro[1002][1002];
int main()
{
int r , c;
while(scanf("%d%d",&r,&c) != EOF)
{
memset(dp , 0 , sizeof(dp));
int i , j;
for(i = 1;i <= r;i++)
for(j = 1;j <= c;j++)
{
scanf("%lf%lf%lf",&pro[i][j].p1,&pro[i][j].p2,&pro[i][j].p3);
}
dp[r][c] = 0;
for(i = r;i >= 1;i--)
{
for(j = c;j >= 1;j--)
{
if(i == r&&j == c) continue;
if(fabs(pro[i][j].p1 - 1) < eps) continue;
dp[i][j] = (dp[i][j+1]*pro[i][j].p2 + dp[i+1][j]*pro[i][j].p3 + 2)/(1 - pro[i][j].p1);
}
}
printf("%.3lfn",dp[1][1]);
}
return 0;
}

最后

以上就是感性鞋子为你收集整理的HDU 3853 LOOPS (概率dp)的全部内容，希望文章能够帮你解决HDU 3853 LOOPS (概率dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。