HDU 3853

 1 // 第一次做概率DP，根本不懂。。。看了题解还是不懂。尼马！！！！！！
 2 
 3 //只是听人家说什么求概率要正推，求期望要逆推。。。尼马还是不懂！！！！
 4 
 5 //于是找了个水题做了一个，特么的还是不懂！！！！
 6 
 7 //这是个开始，，，慢慢来
 8 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
 9 #include<stdio.h>
10 
11 #include<string.h>
12 #include<math.h>
13 #define max 1000+5
14 #define eps 1e-10
15 
16 struct node{
17     double h,r,d;
18 }map[max][max];
19 double dp[max][max];
20 int r,c;
21 
22 void solve(){
23     for(int i=r;i>=1;i--){
24         for(int j=c;j>=1;j--){
25             if(i==r&&j==c){
26                 continue;
27             }
28             if(fabs(1-map[i][j].h)<eps){
29                 continue;
30             }
31             double res1=map[i][j].r*dp[i][j+1];
32             double res2=map[i][j].d*dp[i+1][j];
33             dp[i][j]=(res1+res2+1)/(1-map[i][j].h);
34         }
35     }
36 }
37 
38 int main(){
39     while(~scanf("%d%d",&r,&c)){
40         memset(map,0,sizeof(map));
41         for(int i=1;i<=r;i++){
42             for(int j=1;j<=c;j++){
43                 node& t=map[i][j];
44                 scanf("%lf %lf %lf",&t.h,&t.r,&t.d);
45             }
46         }
47         memset(dp,0,sizeof(dp));
48         //dp[r][c]=0;
49         solve();
50         printf("%.3lf
",2*dp[1][1]);
51     }
52 }