首页 > 其他 > 详细

【HDOJ】【3853】LOOPS

时间:2015-02-26 13:20:13      阅读:298      评论:0      收藏:0      [点我收藏+]

概率DP

  kuangbin总结中的第7题

  其实跟UVA 11762 Race To 1 那道题差不多……直接推下公式,然后倒推即可

 

Trick:有的点可能是p1[i][j]==1……这样的点是永远不会走出去的……所以也不能走到……遇到这样的点直接跳过就好了TAT

    但是!!浮点数不能直接判定相等……应该写成 fabs(1-p[i][j][0])<eps 来判定!!!sad……

技术分享
 1 //HDOJ 3853
 2 #include<cmath>
 3 #include<cstdio>
 4 #define F(i,j,n) for(int i=j;i<=n;++i)
 5 #define D(i,j,n) for(int i=j;i>=n;--i)
 6 
 7 const int N=1100,INF=~0u>>2;
 8 const double eps=1e-5;
 9 double f[N][N],p[N][N][3];
10 
11 int main(){
12     int n,m;
13     while(scanf("%d%d",&n,&m)!=EOF){
14         F(i,1,n) F(j,1,m) F(k,0,2)
15             scanf("%lf",&p[i][j][k]);
16         f[n][m]=0;
17         D(i,n,1)
18             D(j,m,1){
19                 if (i==n && j==m) continue;
20                 if (fabs(1-p[i][j][0])<eps) continue;
21                 double *P=p[i][j];
22                 f[i][j]=2/(1-P[0]) + f[i][j+1]*P[1]/(1-P[0]) + f[i+1][j]*P[2]/(1-P[0]);
23             }
24         printf("%.3lf\n",f[1][1]);
25     }
26     return 0;
27 }
View Code

 

【HDOJ】【3853】LOOPS

原文:http://www.cnblogs.com/Tunix/p/4300996.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!