首页 > 其他 > 详细

hdu 3853 LOOPS (概率dp)

时间:2015-02-23 10:48:26      阅读:254      评论:0      收藏:0      [点我收藏+]
/*
dp[i][j]表示(i,j)到(R,C)须要消耗的能量
则:
dp[i][j]=p1[i][j]*dp[i][j]+p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2;///+2 转移到下一个能量要消耗2
化简得:
dp[i][j]=((p2[i][j]*dp[i][j+1])+(p3[i][j]*dp[i+1][j])+2)/(1-p1[i][j]);
*/
# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <iostream>
using namespace std;
double dp[1010][1010],p1[1010][1010],p2[1010][1010],p3[1010][1010];
int main()
{
    int r,c,i,j;
    while(~scanf("%d%d",&r,&c))
    {
        for(i=1;i<=r;i++)
        {
            for(j=1;j<=c;j++)
                scanf("%lf %lf %lf",&p1[i][j],&p2[i][j],&p3[i][j]);
        }
        dp[r][c]=0;
        for(i=r;i>=1;i--)
        {
            for(j=c;j>=1;j--)
            {
                if(i==r&&j==c)
                    continue;
                if(p1[i][j]==1)
                    continue;
                dp[i][j]=((p2[i][j]*dp[i][j+1])+(p3[i][j]*dp[i+1][j])+2)/(1-p1[i][j]);
            }
        }
        printf("%.3lf\n",dp[1][1]);
    }
    return 0;
}

hdu 3853 LOOPS (概率dp)

原文:http://www.cnblogs.com/bhlsheji/p/4297899.html

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